174. Dungeon Game

Problem Link

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]