# Need some help to find recursive and dp solution for SPOJ BORW BlackOrWhite Problem

Hi,
I have been trying to find the recursive solution for SPOJ BORW(Black or White) problem , but none of the recursive logic seems to work.
I understood that the recursive equation will be based on the logic that any ball can be either painted black or white or none , but couldn’t turn it into logical terms .

Since recurisve solution has been provided now , I was trying to convert this solution to dp solution using 3D dp array of which one of the state whould be array index. For the next two states I am little confused bcoz if I take array values as the other two indexes , then the dp size would be too large . Any suggestion what should be the other two states of dp ??
Any hints will be appreciated. Thanks

I have tried to implement the solution here : Link.
In case of any doubt feel free to ask!

1 Like

@vivek_1998299 , thanks for your response,
i too didn’t get how this algorithm is working , although i tried to created one solution with your algo , but it is not working . Please have a look and suggest me what changes are required ??

@vivek_1998299 , thanks for your response,
i too didn’t get how this algorithm is working , although i tried to created one solution with your algo , but it is not working . Please have a look and suggest me what changes are required ??

Hi dishant . thanks a lot for your resposne. I guess i got confused in making this recursive solution bcoz i was trying to implement dp along with recursion ( feeling a lot silly now) . thanks anyway

Infact I too am trying to figure out a dp solution to this since yesterday (yeah I am pretty bad at dp xD).
Have you figured out one yet? If yes please share it!

U can easily do this using 2d Dp,dp[x][y] denotes the maximum number of painted if the xth ,and yth index are the last in increasing and decreasing subsequences.

dp[x][y]=max(dp*[y]+1)–>(for i<x and arr*<arr[x])

dp[x][y]=max(dp[x]+1)—>(for i<y and arr>arr[y])

Can you explain a bit more on this and maybe provide pseudocode. I can’t get how this works!

I tried implementing your logic but it didn’t worked. Can you plz see into the code to figure out where I’m going wrong. Code