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?