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

nandm?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 costk. Then the answer isdp[c][d][m].But in general you should give bounds or at least a ballpark of the complexity you are expecting.