Dungeon Game Python Solution with Tests

lcpy gen -n 174   # by problem number
lcpy gen -s dungeon_game   # by problem name

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT -> RIGHT -> DOWN -> DOWN.

Input: dungeon = [[0]]
Output: 1

class Solution:
    # Time: O(m * n)
    # Space: O(n)
    def calculate_minimum_hp(self, dungeon: list[list[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        # need[j]: minimum health required upon entering cell (i, j); right
        # sentinel need[n] = INF means "no cell to the right" outside the grid.
        need = [10**9] * (n + 1)
        need[n - 1] = 1
        for i in range(m - 1, -1, -1):
            need[n] = 10**9
            for j in range(n - 1, -1, -1):
                need[j] = max(1, min(need[j], need[j + 1]) - dungeon[i][j])
        return need[0]