# Dp problem help

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 …

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

``````int dp[n+1];
dp = 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

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 ??

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

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