Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### ay2306's blog

By ay2306, history, 5 months ago, ,

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?

•
• -3
•

 » 5 months ago, # |   0 Bounds on n and m?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 months ago, # ^ |   +3 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.