如何加快/修复此最短路径网格遍历？

Question

我正在编写一个程序，从左下角到右上角遍历网格，其中有效移动是向右移动1，向上移动1，或向上或向右跳跃跳跃跳跃数组中指定的数量。输入是2D数组格式的网格、网格的尺寸：X和Y，以及必须按顺序完成跳转的跳转数组。输出是最短路径，其中路径的长度是所有接触的数字的总和，包括左下角和右上角
示例输入：

Grid: 
    [9 9 1]
    [9 9 1]    
    [3 9 1]

Jumps: [1 1] X:3, Y:3

输出是5，因为我们从（0,0）开始，它是3，然后使用第一个1块跳转到（2,0），它是1，然后第二个1块跳转到（2,2），它是1，所以3 1 1=5.如果跳跃数组只有[1]，那么输出将是6，因为我们必须从（2,0）到（2,1）再到（2,2）。

这是我的第一个解决方案，它似乎适用于较小的输入，但只适用于较大的输入：

def get(grid, x, y, endX, endY):
    if (x > endX or y > endY):
        return False
    return grid[y][x]

def fly(x, y, grid, jumps, endX, endY):
    if x > endX or y > endY:
        return float('inf')
    if (x == endX and y == endY):
        return get(grid, endX, endY, endX, endY)
    flyup = fly(x, y+1, grid, jumps, endX, endY)
    flyright = fly(x+1, y, grid, jumps, endX, endY)
    if (len(jumps) > 0):
        jumpup = fly(x, y+jumps[0]+1, grid, jumps[1:], endX, endY)
        jumpright = fly(x+jumps[0]+1, y, grid, jumps[1:], endX, endY)
        temp = min(flyup, flyright, jumpup, jumpright)
        return get(grid, x, y, endX, endY) + temp
    else:
        temp = min(flyup, flyright)
        return get(grid, x, y, endX, endY) + temp

fly(0, 0, grid, jumps, X-1, Y-1)

这是我用DP写的另一个解决方案（或者我刚学DP时对DP的理解是什么），但这个解决方案似乎只适用于某些输入，我无法识别模式。

def fly2(x, y, grid, jumps):
    dp = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if row == 0 and col == 0:
                dp[row][col] += get2(grid, col, row)
            else:
                flyup = float('inf') if row==0 else dp[row-1][col]
                flyright = float('inf') if col==0 else dp[row][col-1]
                jumpup =  float('inf') if row < jumps[0]+1 else dp[row-jumps[0]-1][col]
                jumpright =  float('inf') if col < jumps[0]+1 else dp[row][col-jumps[0]-1]
                shortest = min(flyup, flyright, jumpup, jumpright)
                if min == jumpup or min == jumpright:
                    jumps = jumps[1:]
                dp[row][col] += get2(grid, col, row) + shortest
    return dp[len(grid)-1][len(grid[0])-1]

我需要一些帮助来加快第一个，或者找出第二个有什么问题，或者也许得到一些关于如何有效地写这个的其他想法。谢啦

Answer 1

以下实现使用网格和剩余的跳跃作为状态变量：

import numpy as np

def shortest(grid, jumps):
    rows, cols = grid.shape
    if (rows, cols) == (1, 1): # if grid is just a single number
        return float('inf') if jumps else grid[0, 0]
    candidates = [] # store results from deeper calls
    if rows > 1:
        candidates.append(shortest(grid[:-1, :], jumps)) # up by one
        if jumps and rows > jumps[0] + 1: # jump to the above if possible
            candidates.append(shortest(grid[:-(jumps[0] + 1), :], jumps[1:]))
    if cols > 1:
        candidates.append(shortest(grid[:, 1:], jumps)) # right by one
        if jumps and cols > jumps[0] + 1: # jump to the right if possible
            candidates.append(shortest(grid[:, (jumps[0] + 1):], jumps[1:]))
    return grid[-1, 0] + min(candidates)

grid = np.array([[9, 9, 1], [9, 9, 1], [3, 9, 1]])
jumps = [1, 1]
print(shortest(grid, jumps)) # 5

使用np.array只是为了简化切片。

Answer 2

在我看来，dp对于当前的跳跃指数应该有另一个维度。通常地

dp[y][x][j] = Grid[y][x] + min(
  dp[y + 1][x][j],
  dp[y][x - 1][j],
  dp[y + jump[j-1] + 1][x][j-1],
  dp[y][x - jump[j-1] - 1][j-1]
)

其中j是跳转数组中的当前索引。

（我认为问题描述在例子中使用了（x，y）坐标表示法。我使用[y][x]作为[行][列]，常用于编程二维数组访问。（