kofhearts's blog

help with dp equation
By kofhearts, 10 years ago, In English

hello everyone,

I am having trouble understanding 3 dimensional dp. I can understand 2 dimensional dp but i am having trouble coming up with the objective function for this dp. Can someone please explain me what the state function will be like? I know the i, j position of the matrix will be two variables and the third variable will be remainder but i don't get how these three variables can be used to obtain the transition equation. I am especially having problem understanding dp with mod operation like this. I appreciate any help!

http://codeforces.com/contest/41/problem/D

I will summarize the problem.

Suppose there is a grid with number of coins in each cell.

1 2 3

4 5 6

7 8 9

There is a pawn in the bottom most row. Now the pawn can move either top right (eg.suppose if the pawn is at 8 he can move to 6(top right)) or top left(eg.suppose if the pawn is at 8 he can move to 4(top left)). The goal is to reach the top most row. Here is one way to do so. 8, 4, 2. Now we add all the coins that we received while landing to a cell.

The goal is to maximize this sum. The pawn has to start from the bottom most row and we can start from any cell from that row.

If this was the only question then i think it is straight forward 2 dimensional dp but the twist is that the maximum sum also has to be divisible by k. So, if s is the sum then s % k has to be 0.

I'd appreciate if anyone can explain to me the 3d dp solution. I don't seem to understand dp with mods. Thanks!

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

when you are in position (i,j) either you come from (i-1,j-1) or (i-1,j+1) so the value of do[i][j][k] depends on dp[i-1][j-1][u] and dp[i-1][j+1][u] where u is the number that if you added it to A[i][j] then took the answer modulo (the number of bothers of the pown + him self) it will become k. so dp[i][j][k]=max(dp[i-1][j-1][u],dp[i-1][j+1][u])+A[i][j];

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Not sure what is the exact problem with understanding 3d DP if you're ok with 2D dp, the difference is pretty minor here:

  1. For 2D DP[i][j] you will store the maximum score you can achieve when coming to the cell (i, j).

  2. In this case for 3D you will have DP[i][j][m] which will be the maximum score you can achieve when coming to the cell (i, j) if that score modulo k gives m.

Highlighted is the difference. This definition of what is DP[i][j][m] in this problem should be enough to understand how to build this DP and which value to take as the result.

→ Reply