getting wa in dp problem

thanks in advance

Hello good day to you. Sorry I didn’t get time going through your code. But in case you want an explanation on how to solve that problem:

Okay so i will represent my current state by a flag, which is 0 if my last column was white else it is 1.
Also 2 more parameters are needed namely N and curr, curr being the current length of the last state. Now lets just focus on 1 state say white and the case for black is almost same. Now if my curr==z that is I can no more take a white column, my cost in this column will be number of white cells as they will be the one that needs to be changed. So in this case:

dp[N][curr][flag]=go(N-1,1,1)+(no of white cells in Nth column)

Now if curr < y, I need more white columns , so my current column must be a white one

dp[N][curr][flag]=go(N-1,curr+1,0)+(no of black cells in Nth column)

Else , my current column can be either black or white. So,

dp[N][curr][flag]=min(go(N-1,curr+1,0)+(no of black cells),go(N-1,1,1)+(no of white cells))

You can have a look at my code for implementation : here

1 Like

I am implementing the same thing.
In my approach I have taken the cost of converting each column into white or black and at each point in recursion I am considering that the next space will be black or white and using the same form of dp you are.
So I would like to request to you to have a look at my code

tried your approach, still getting wa