I am working on a question like, there is given a m × n grid. Each cell holds value. What is the total number of paths from (a, b) to (c, d) given the sum of the values of cell in the path is m.
Possible movements from (i, j) are (i, j)→(i + 1, j), (i, j)→(i−1, j), (i, j)→(i, j + 1), (i, j)→(i, j−1)
I know it can be solved with dynamic programming but I was too much confused to what should I store. Because as contrasting to maximum cost path, it was not a stable value. What should I do in such case?
Bounds on n and m?
Actually, I am asking as a general question, the one which can cover comparatively bigger bounds. Though question asked 20x20, I want to learn for bigger constraints as well.
Well, one way is defining dp[i][j][k] as the number of paths from (a, b) to (i, j) with cost k. Then the answer is dp[c][d][m].
But in general you should give bounds or at least a ballpark of the complexity you are expecting.