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]