Problem: B - Extension
Initially I came up with the following DP relation, DP[i][j] = DP[i-1][j]*j + DP[i][j-1]*i, where DP[i][j] is the number of ways to color a i x j grid, with the base cases as DP[i][j] = 0 if either i or j is less than A or B respectively and DP[i][j] = 1 if i = A and j = B.
Now, when I coded the solution I got the wrong answer for the first sample test case itself, the reason being that it counted the repeating solutions as well. So when I looked on the internet for the correct DP relation I got this,
DP[i][j] = DP[i-1][j]*j + DP[i][j-1]*i - DP[i-1][j-1]*(i-1)*(j-1)
.So the difference is in the last term, and that is what I am finding a little difficult to understand.
Can anyone please explain that last term, how does it help in eliminating the repeating solutions (coloring)? And how does one arrive at that?
Notice that for dp_{i-1,j}\times i and dp_{i,j-1} \times j to be exactly same, requires the top row, and the rightmost column to have exactly one black square.
That means the there shouldn’t have been any black square on put on the column/row.
That would imply that the number of ways to make the inner grid is dp_{i-1,j-1}.
This is because we weren’t actually allowed to put a black square on the row or column which we may have put first, so the number of ways to make the inner grid, was not affected by that addition. so the number of ways to make the inner grid is still dp_{i-1,j-1}.
So after that we notice that if a black square is put on the intersection of the current topmost row and right most column, it must have exactly one order. If it’s not, then they may have been added in any order. since there are i-1 spots for the black square to go on the top row, and j-1 black squares to go on the rightmost column We get dp_{i-1,j-1} \times (i-1) \times (j-1)
1 Like