Color a 3XN grid using atmost 4 colors DP Problem help needed

Revision en1, by aman_naughty, 2019-07-22 22:35:49

Problem : link

Code : code

My approach is : For any {i,j} I maintain 4 colors dp[i][j][0],dp[i][j][1],dp[i][j][2] and dp[i][j][3];

dp[i][j][k] denotes the number of ways to fill the board[0..i][0..j] using the color k at position i,j.

To fill dp[i][j][k] we need only summation of (dp[i-1][j][l]+dp[i][j-1][l]) where l varies from 0 to 3 and l is not equal to k.

In simple words to fill i,j with color k number of ways would be we can fill i-1,j with color other than k and i,j-1 with color other than k.

In the end my answer would be summation of dp[3][n][k] where 0<=k && k<=3;

Why is this approach wrong as I am getting wrong answer for n=2 test case?

Any help is appreciated.

Tags #interview, #2d-dp, codenation, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aman_naughty 2019-07-22 22:35:49 871 Initial revision (published)