题解 | 龙与地下城游戏问题

def calculate_minimum_hp(map):
    m, n = len(map), len(map[0])
    # 初始化动态规划表
    dp = [[0] * n for _ in range(m)]

    # 初始化终点
    dp[m - 1][n - 1] = max(1, 1 - map[m - 1][n - 1])

    # 初始化最后一列
    for i in range(m - 2, -1, -1):
        dp[i][n - 1] = max(1, dp[i + 1][n - 1] - map[i][n - 1])

    # 初始化最后一行
    for j in range(n - 2, -1, -1):
        dp[m - 1][j] = max(1, dp[m - 1][j + 1] - map[m - 1][j])

    # 填充动态规划表
    for i in range(m - 2, -1, -1):
        for j in range(n - 2, -1, -1):
            # 选择向右或向下移动所需的最小初始血量
            min_required = min(dp[i + 1][j], dp[i][j + 1])
            dp[i][j] = max(1, min_required - map[i][j])

    # 返回结果
    return dp[0][0]


# 输入处理
n, m = map(int, input().split())
matrix = []
for _ in range(n):
    row = list(map(int,input().split()))
    matrix.append(row)

# 计算最小初始血量
result = calculate_minimum_hp(matrix)
print(result)