使用向右或向下跳跃或单位步数在网格中的最小成本路径

Question

假设您有一个网格，其中每个节点都包含一个权重，该权重表示获取该正方形的成本。

从二维数组左上角的（0,0）开始，然后到达（X-1，Y-1），其中X是列数，Y是右下角的行数。你可以向右走1平方米，也可以一次向下走1平方米。您还将获得一个整数“跳跃”数组，其中每个值$d_i$表示您可以在第i次跳跃时向右或向下跳过的方块数。跳转数组指定跳转的顺序，这意味着，例如，如果没有使用一个跳转，则不能跳转[2]。您只能进行len（jump）次跳跃。

我们正试图用动态规划来解决这个问题。这就是我迄今为止所做的：

def helper(grid, jumps):
    dCount = 0
    dp = [[[0 for k in range(len(jumps)+1)] for j in  range(len(grid[0]))] for i 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][dCount] += grid[row][col]
            jumpRight = float('infinity')
            jumpUp = float('infinity')
            goUp = float('infinity')
            goRight = float('infinity')
            if(row > 0):
                goUp = dp[row-1][col][dCount]
            if(col > 0):
                goRight = dp[row][col-1][dCount]
            if (dCount < len(jumps)):
                jumpRight = dp[row-jumps[dCount]][col][dCount] 
                jumpUp = dp[row][col-jumps[dCount]][dCount]
            res = grid[row][col] + min(goRight, goUp, jumpRight, jumpUp)
            if(res == jumpRight or res==jumpUp): 
                dCount+=1
            dp[row][col][dCount] = res
    return dp[len(grid)-1][len(grid[0])-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)) #should be 16

然而，代码似乎不起作用。

上面只是打印出[0 0 15]，而我认为应该是[0 0 16]

Answer 1

下面是一个自底向上方法的示例，它似乎返回了本例和类似问题中的正确结果。不过，我不确定代码是否万无一失。

Python：

def f(grid, jumps):
  m, n = len(grid), len(grid[0])
  dp = [None] * m

  for i in range(m):
    dp[i] = [[float('inf')] * (len(jumps) + 1) for j in range(n)]

  dp[0][0][0] = grid[0][0]

  for y in range(m):
    for x in range(n):
      for j in range(len(jumps) + 1):
        if (y, x, j) == (0, 0, 0):
          continue

        dp[y][x][j] = grid[y][x] + min(
          dp[y - 1][x][j] if y > 0 else float('inf'),
          dp[y][x - 1][j] if x > 0 else float('inf'),
          dp[y - jumps[j-1] - 1][x][j-1] if (j > 0 and y - jumps[j-1] - 1 >= 0) else float('inf'),
          dp[y][x - jumps[j-1] - 1][j-1] if (j > 0 and x - jumps[j-1] - 1 >= 0) else float('inf')
        )
  
  return min(dp[m-1][n-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(f(grid, jumps)) # 16


grid = [
  [3, 9, 1],
  [9, 9, 1],
  [9, 9, 1]
]

jumps = [1, 1]

print(f(grid, jumps)) # 5

Answer 2

以下是一个实施方案：

def shortest(grid, jumps, x=0, y=0, jumped=0):
    # grid: whole grid
    # jumps: jumps to be exhuasted
    # x, y: current position
    # jumped: number of jumps that have been used
    # output: a tuple (cost, path)
    #         cost: minimum cost from this position to the final position
    #         path: a list of tuples, each element the position along the minimum-cost path
    rows = len(grid) - x; cols = len(grid[0]) - y # remaining num of rows and cols
    if (rows, cols) == (1, 1): # if arrived at the southeast corner
        return (float('inf'), [(x, y)]) if jumps[jumped:] else (grid[x][y], [(x, y)]) # return inf if jumps are not exhausted
    candidates = [] # store results from deeper calls
    if rows > 1: # if possible to move down
        candidates.append(shortest(grid, jumps, x+1, y, jumped)) # down by one
        if jumped < len(jumps) and rows > jumps[jumped] + 1: # if possible to jump
            candidates.append(shortest(grid, jumps, x+jumps[jumped]+1, y, jumped+1)) # jump down
    if cols > 1: # if possible to move right
        candidates.append(shortest(grid, jumps, x, y+1, jumped)) # right by one
        if jumped < len(jumps) and cols > jumps[jumped] + 1: # if possible to jump
            candidates.append(shortest(grid, jumps, x, y+jumps[jumped]+1, jumped+1)) # jump right
    temp = min(candidates, key=lambda x: x[0]) # recall: temp[0]: min_cost, temp[1]: min_path
    return (temp[0] + grid[x][y], [(x, y), *temp[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(shortest(grid, jumps)) # (16, [(0, 0), (0, 1), (0, 2), (0, 4), (2, 4), (2, 5), (3, 5)])

状态变量是x，y和跳转；x和y记住当前位置在给定网格中的位置。跳转记住有多少次跳转到目前为止使用。

递归的结束状态发生在位置位于最终目的地时，即[-1，-1]。如果跳跃尚未用尽，则为失败；因此，返回无穷大作为代价。否则，返回该点的值作为成本。

实际上，返回是一个元组；第一个元素是成本，第二个元素是当前位置。第二个元素用于最终获得成本最小化路径。

在其他状态下，递归是以自然的方式定义的；该函数递归为（最多）四种可能的移动：向上移动一次，向右移动一次，向上跳，向右跳。它比较结果成本，并选择最小成本方向。

注意：这使用了python 3.5中引入的通用解包。但这并不重要。