## Leetcode 174

Posted on 09 Mar 2017
dynamic programming

### Tutorial

The knight should at least have 1 health and can only move to right and down. dp[i][j] means how many points are needed in order to rescue the princess from grid[i][j]. dp[i][j] = min(max(1, dp[i + 1][j] - dungeon[i][j]), max(1, dp[i][j + 1] - dungeon[i][j]))

### Solution

class Solution(object):
def calculateMinimumHP(self, dungeon):
"""
:type dungeon: List[List[int]]
:rtype: int
"""
row_num = len(dungeon)
col_num = len(dungeon[0])
dp = [[0] * col_num for i in range(row_num)]
dp[row_num - 1][col_num - 1] = max(1, -dungeon[row_num - 1][col_num - 1] + 1)

for i in range(row_num - 1)[::-1]:
dp[i][col_num - 1] = max(1, dp[i + 1][col_num - 1] - dungeon[i][col_num - 1])

for i in range(col_num - 1)[::-1]:
dp[row_num - 1][i] = max(1, dp[row_num - 1][i + 1] - dungeon[row_num - 1][i])

for i in range(row_num - 1)[::-1]:
for j in range(col_num - 1)[::-1]:
a = max(1, dp[i + 1][j] - dungeon[i][j])
b = max(1, dp[i][j + 1] - dungeon[i][j])
dp[i][j] = min(a, b)

return dp[0][0]