Dp problem help

general
1

hi codechef comunity …someone plz help me in the problem:

 https://codeforces.com/contest/1037/problem/C

if anyone has dp approach to solve it please do share … i have been trying for days but i am not able to get dp approach … i have got AC with greedy approach …

2

For every bit maintain a dp array dp[i][2],(for different bits) for dp[i][0]=1+min(dp[i-1][0],dp[i-1][1]); and for dp[i][1]=1+min(dp[i-2][0],dp[i-2][1]) if swapping conditions are satisfying else
dp[i][1]=dp[i][0] (for same bits) copy from previous values,
Answer will be min(dp[n-1][0],dp[n-1][1])

3 
int dp[n+1];
dp[0] = 0  
for (int x = 1; x<= n; x++){
      if(a[i-1] == b[i-1]) dp[i] = dp[i-1];l
      else {
            dp[i] = dp[i-1] + 1;
            if(a[i-2] == b[i-1] && a[i-1] ==b[i-2] )
                 dp[i] = min(dp[i-2] + 1, dp[i]);
      }
   }
cout << dp[n]
}

logic is simple all |i - j| >= 2 will give the optimal answer by operation 2

1 Like
4

thank you so much for helping me … i have done using this way already .(greedy way) …
i was asking if i do not apply this logic (greedy) and go on solving all the possible cases and finding out the minimum using dp approach in given time complexity ??

6

could u please explain me the recurrence and be more detailed ?? thanks for the help brother

7

LETS SAY YOU WANNA TO SWAP I, j SUCH THAT |i - j| >= 2
IN THAT CASE COST WILL BE => 2, WHICH IS THE LOWER BOUND OF FLIPPING THE I,j VALUE ITSELF