Блог пользователя ay2306

Автор ay2306, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Bounds on n and m?

  • »
    »
    6 лет назад, # ^ |
    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.