ay2306's blog

Solving grid questions.
By ay2306, history, 6 years ago, In English

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?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bounds on n and m?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

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

      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.

      → Reply