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

DP problem (Top down vs bottom up)
Автор rr459595, история, 5 лет назад, По-английски

I tried solving this problem on leetcode ( https://leetcode.com/problems/dungeon-game/ ). I got AC with bottom up approach but wrong answer with top down approach.

Can someone help me in proving why only bottom up approach works and not top down (tabulating values from top left to bottom right)?

Thank you.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

In top-down, how would you check if you reach health 0 at some moment? You don't know your current health.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    By top down, I meant that I would fill the table by filling dp[i][j] using dp[i][j-1] and dp[i-1][j] where dp[i][j] is min health required to reach (i,j) from (0,0). I think that the definition of dp(i,j) as min health required to reach (i,j) from (0,0) is incorrect (using counter-example). But I am not able to prove why dp(i,j) should be defined as min health from (i,j) to (n-1,n-1) instead of (0,0) to (i,j).

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      Ok, I think I understood the issue.

      When you got from (0, 0) to (i, j), there are two important things: minimum health so far (that defined the initial boost we need to survive) and the final health. You can't maximize both at the same time and only future moves would tell you which one was more important. On the other hand, going from (i, j) to (n-1,n-1) you only maximize the required boost to survive, i.e. the minimum possible starting health with which you would survive.

      → Ответить