Minimum HP

The main idea is to use recursion to reduce the big problem into several smaller subproblems.

Algorithm :

1. We will call a minimumHealth function that returns us the minimum health required from the current point to destination ('N' - 1, ‘M’ - 1).
2. From each point ('i', ‘j’), we have 2 choices:
   • We can move right to ('i' , ‘j’ + 1). Then we will do a recursive call with ('i', ‘j’ + 1) as our starting point, say the minimum health required from this call comes out to be ‘op1’.
   • Or we can move down to ('i' + 1, ‘j’). Then we will do a recursive call with ('i' + 1, ‘j’) as our starting point, say the minimum health required from this call comes out to be ‘op2’.
   • our minimum health required from ('i' , ‘j’) to ('N' - 1, 'M' - 1) will be ‘board[i][j]' + min('op1', 'op2').
3. The algorithm for minimumHealth will be as follows:
   • Int minimumHealth(‘board’, ‘i’, ‘j’, ‘N’, 'M)
     • If ‘i’ >= ‘N’ or ‘j’ >= ‘M’ :  if the point is out of grid.
       • return large integer value
     • If  ‘i’ == ‘N’ - 1 and j == ‘M’ - 1:
       • if board[i][j]' ≤ 0:
         1. return abs(board[i][j])+ 1
       • else:
         1. return 1
     • int ‘op1’ = minimumHealth (board, 'i', 'j' + 1, ‘N’, ‘M’)
     • int 'op2' = minimumHealth (‘board, ‘i’ + 1, ‘j’, ‘N’, ‘M’)
     • int minHealthRequired = min(op1, op2) - board[i][j];
       • if minHealthRequired ≤ 0:
         1. return 1
       • else
         1. return minHealthRequired.

We can see that we were solving the same subproblems multiple times. Thus, this problem was exhibiting overlapping subproblems. This means, in this approach, we need to eliminate the need to solve the same subproblems repeatedly. Thus, the idea is to use Memoization.

Algorithm :

The steps are as follows:

1. Create a ‘dp’ table of size ‘N’ * ‘M’ to store the answers to the subproblems where ‘dp[i][j]’ denotes minimum health required from ('i', 'j') to ('N' - 1, 'M' - 1)
2. Initialize the ‘dp’ array with -1 which denotes that it is not calculated yet.
3. We will call a minimumHealth function that returns us the minimum path sum.
4. The algorithm for minimumHealth will be as follows:
   • Int minimumHeath('board', ‘i’, ‘j’, ‘N', ‘M’)
     • If 'i' >= ‘N’ or ‘j’ >= 'M' : if the point is out of grid.
       • return a large integer value
     • If  ‘i’ == ‘N’ - 1 and ‘j’ == ‘M’ - 1:
       • if ‘board[i][j]' ≤ 0:
         1. return abs(board[i][j] + 1
       • else:
         1. return 1
     • If ‘dp[i][j]’ != -1: means we have already calculated the answer for this sub-problem,
       • return ‘dp[i][j]’.
     • Int ‘op1’ = minimumHealth(‘board’, ‘i’, ‘j’ + 1, ‘N’, 'M')
     • Int ‘op2’ = minimumHealth('board', 'i' + 1, 'j', ‘N’, ‘M’)
     • int minHealthRequired = min(op1, op2) - board[i][j];
     • if minHealthRequired ≤ 0:
       • dp[i][j] = 1
     • else
       • dp[i][j] = minHealthRequired
     • Return 'dp[i][j]'.

• We will create a DP solution where dp[i][j] = minimum health needed from position (i, j) to reach position (n - 1, m - 1)
• If we were to have only 1 value in the board ( i.e. N = 1, and M = 1) then the minimum initial hp required will have been = -board[0][0] +1. Therefore, dp[n - 1][m - 1] = 1- board[n - 1][m - 1]. Here 1 is added because we cannot have our hp reach 0.
• From position (i, j) we can move to position (i + 1, j) and position (i, j+1). Thus we can find the value of dp[i][j] from dp[i + 1][j] and dp[i][j + 1].
• After moving from (i, j) to (i + 1, j) we are gaining board[i + 1][j] hp. Conversely if we were to move from (i+1, j) to (i, j) we can look at it as losing board[i + 1][j] hp. Thus dp[i][j] may be dp[i + 1][j] - board[i][j].
• Similarly dp[i][j] may be dp[i][j + 1] - board[i][j]. Or more specifically it will be the minimum of the two.
• Do note if at any time our minimum initial hp becomes 0 or less, we set our minimum hp as 1 because initially we can’t have 0 hp.

Algorithm:

• Create a ‘dp’ table of size N*M.
• Set dp[n - 1][m - 1] =max(1,  1- board[n - 1][m - 1]).
• Fill values in the last row in backward direction, for j={M-2,…, 0},
  • dp[n - 1][j] = max(1, dp[n - 1][j + 1] - board[n - 1][j] ).
• Fill values in the last column in backward direction, for i={N - 2,…, 0},
  • dp[i][M - 1] = max(1, dp[i + 1][M - 1] - board[n - 1][j]) .
• For i in {N - 2,…..,0}:
  • For j in {M - 2,....,0}:
    • dp[i][j]= min( max(1,dp[i + 1][j] - board[i][j] ), max(1,dp[i][j + 1]-board[i][j]))
• Return dp[0][0]