可使用跳跃/右/下单位步的网格最小成本路径DP代码调试

原代码的核心错误有4处：

• 全局共用dCount变量统计跳跃次数完全错误。动态规划的第三维本来设计为记录「已使用k次跳跃」的状态，但全局计数器强行让所有路径的跳跃次数同步，忽略了不同路径到达同一位置时跳跃次数不同的可能。
• 未做跳跃合法性校验：跳跃d步时未判断上一个位置的坐标是否≥0，会出现数组下标越界、取到无效值的问题。
• 跳跃方向逻辑错误：jumpRight变量对应了向上跳的逻辑，jumpUp对应了向左跳的逻辑，方向完全写反。
• dp数组初始化错误：除起点外的所有状态初始值应为无穷大，原代码初始化为0会导致最小值计算时取到错误结果。

我们定义dp[i][j][k]为到达坐标(i,j)、且已经使用了k次跳跃时的最小成本，遍历所有位置和所有可能的跳跃次数分别计算状态即可：

def helper(grid, jumps):
    Y = len(grid)
    X = len(grid[0])
    max_jump = len(jumps)
    # 初始化所有状态为无穷大
    dp = [[[float('inf')] * (max_jump + 1) for _ in range(X)] for __ in range(Y)]
    dp[0][0][0] = grid[0][0]
    
    for i in range(Y):
        for j in range(X):
            for k in range(max_jump + 1):
                # 跳过未初始化的无效状态
                if dp[i][j][k] == float('inf'):
                    continue
                # 普通走步：向下走1步
                if i + 1 < Y:
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + grid[i+1][j])
                # 普通走步：向右走1步
                if j + 1 < X:
                    dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k] + grid[i][j+1])
                # 还有剩余跳跃次数，可以使用第k次跳跃
                if k < max_jump:
                    d = jumps[k]
                    # 向下跳d步
                    if i + d < Y:
                        dp[i+d][j][k+1] = min(dp[i+d][j][k+1], dp[i][j][k] + grid[i+d][j])
                    # 向右跳d步
                    if j + d < X:
                        dp[i][j+d][k+1] = min(dp[i][j+d][k+1], dp[i][j][k] + grid[i][j+d])
    # 到达终点的所有可能跳跃次数的最小值就是答案
    return min(dp[Y-1][X-1])

grid = [[1, 0, 3, 7, 2, 5], [8, 3, 7, 6, 9, 8], [9, 7, 8, 2, 1, 1], [3, 2, 9, 1, 7, 8]]
jumps = [1, 1]
print(helper(grid,jumps)) # 输出16

内容的提问来源于stack exchange，提问作者anon comp