rr459595's blog

DP problem (Top down vs bottom up)
By rr459595, history, 5 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    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).

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

      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.

      → Reply