I think there is some mistake in the logic of the solution. Interviewbit and others please have a look


Consider the following test case:
3*4 matrix
-2 -3 3 0
-5 -10 1 0
10 30 -5 -29
Here the expected output is 8, but with my bottom-up approach from top-left I got 7(my solution got accepted). The thing is answer should be -30. How on earth can the knight reach at the end with health of 8? If he goes in this way: Right->Right->Down->Down->Right with starting health of 8, his health at end would be -27 and he dies. If he goes Right->Down-> … at the cell -10 itself his health becomes <0. With top-left approach solution should be as follows:
dp2[i][j]=cost from start to i,j of the path that contains the maximum negative health on the path
dp1[i][j]=maximum negative health in the path from start to i,j
and dp2[i][j]=dp2[i][j-1]+A[i][j] if min(dp1[i][j-1],dp2[i][j-1]+A[i][j])>min(dp1[i-1][j],dp2[i-1][j]+A[i][j])
=dp2[i-1][j]+A[i][j] if min(dp1[i-1][j],dp2[i-1][j]+A[i][j])>min(dp1[i][j-1],dp2[i][j-1]+A[i][j])
=max(dp2[i-1][j]+A[i][j],dp2[i][j-1]+A[i][j]) if both equal from above


Here’s the thing: the knight cannot have a health at any cell below ZERO or he’ll die instantly. So this counters your first argument that the answer should be -30.
Secondly, 8 is the correct answer, check this path out: D->D->R->R->R. Notice how the knight’s health never goes below 0 in the entire path.
I wouldn’t go into details and would leave the question for you to solve yourself, but here are two things you might want to consider:

  • What does dp[i][j] represent in this problem? It is the minimum health power needed for the knight to reach the princess starting from the cell (i, j). Hence our answer would be dp[0][0] if we start from the bottom right A[m-1][n-1] cell.

  • Why do we need to start from bottom right cell instead of top-left? We cannot start from the top left since we do not know the answer to dp[0][0] initially (that is our final answer lol), but we do know the answer to dp[m-1][n-1], and that would be equal to max(1, 1-A[m-1][n-1]). Thus a bottom-up approach would be easier to start off from bottom right corner!


Thanks very much. I got it.