rr459595's blog

By rr459595, history, 4 months ago, ,

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

 » 4 months ago, # |   +1 In top-down, how would you check if you reach health 0 at some moment? You don't know your current health.
•  » » 4 months ago, # ^ | ← 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).
•  » » » 4 months ago, # ^ |   +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.
•  » » » » 4 months ago, # ^ |   0 Yeah,thanks. I understand it now.