Source: Interview
There is grid 'a' of size n*m. There is a guy on cell (1,1) and he wants to reach (n,m). He can move either down or right. Initially, he has health H. If he gets on cell (i,j), then a[i][j] is added to his health. If his health becomes less than or equal to 0, he dies.
Find the minimum value of H so that he can reach the cell (n,m).
I told her binary search but she asked to remove log factor.
How to solve this?
I think you could use dp, where dp[i][j] contains cost of reaching (i, j) using optimal path. By cost I mean minimum value of dp on the path to (i, j). I believe that if at the end dp[n][m]<0, H is equal to -dp[n][m], if dp[n][m]=0, H=1, else H=0. I'm not sure it's 100% correct but I think general idea might be helpful.
Yeah looks similar to Minimum Path Sum — Leetcode problem.
I bet there's many similar problems. I got my idea from a problem: Starting from (1,1) calculate number of paths to (n, n). You can move only right and down.
Yeah
Define $$$D[i][j]$$$ as the minimum health required to start with to travel from $$$(i, j)$$$ to $$$(n, m)$$$.
Then, $$$D[i][j] = max(0, min(D[i + 1][j], D[i][j + 1]) - A[i][j])$$$.