Unable to think of DP solution

#1

What is the recurrence relation?

#2

Let DP(i,j,0) represent Minimum operations needed to color all cells from i to j in same color as ith cell.
Let DP(i,j,1) represent Minimum operations needed to color all cells from i to j in same color as jth cell.

Now let’s think about the transitions.
If you want to calculate dp(i,j,0) then we can use the results dp(i+1,j,0), dp(i+1,j,1), dp(i,j-1,0) and dp(i,j-1,1).

Now Give a try to come up with the recurrence equations and the base cases.

The final ans will be min(dp(1,N,0),dp(1,N,1).

#3

Why do we need to use this 0 and 1 ?

#4

Hi Mridul.
To make the understanding as easy as possible I have used the states i,j,0 and i,j,1. The intuition behind this is if I were to make all elements from i to j of the same color in minimum ops then the last element that joins the connected component will be either i or j and the component will be of that color. Now why do we need this?
let us say I am trying to find out the answer of i,j segment.
then best possible answer for segment i,j will have the segment either in the color of ith cell or in the color of jth cell.

Consider dp(i,j,0) the minimum operations needed to change all cells from i to j such that after all operations they have the color C[i].

dp(i,j,0) = minimum of( !(c[i] == c[i+1]) + dp(i+1,j,0) , !(c[i] == c[j]) + dp(i+1,j,1) , !(c[j] == c[i]) + dp(i,j-1,0), !(c[j-1] == c[j]) + dp(i,j-1,1) ).

I am not saying that it is necessary to have the a boolean to have two seperate states for every i,j but I feel it makes it easier to understand.
Hope this helps :slight_smile:

#5

Very clear now.
Thanks

1 Like
#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.