使用向右或向下跳躍或單位步長的網格中的最小成本路徑

假設您有一個網格，其中每個節點都包含一個權重，表示取該正方形的成本。

您從二維陣列左上角的 (0,0) 開始，然后到達 (X-1, Y-1)，其中 X 是右下角的列數和 Y 行數。您可以向右走 1 個方格，也可以一次向下走 1 個方格。您還將獲得一個 int 陣列“跳轉”，其中每個值 $d_i$ 表示您可以在第 i 次跳轉時向右或向下跳過的方格數。jumps 陣列指定了跳轉時必須采用的順序，這意味著，例如，如果您沒有使用過一個跳轉，則不能采用 jump[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]

uj5u.com熱心網友回復：

下面是一個實作：

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和jumps; x并y記住當前位置在給定網格中的位置。jumps記得到目前為止已經使用了多少跳躍。

遞回的結束狀態發生在位置在最終目的地時，即[-1, -1]。如果跳躍沒有用盡，則為失敗；所以回傳無窮大作為成本。否則，回傳該點的值作為成本。

實際上，回傳的是一個元組；第一個元素是成本，第二個元素是當前位置。第二個元素用于最終獲得成本最小化路徑。

在其他狀態下，遞回以自然的方式定義；該函式遞回到（最多）四種可能的運動：向上，向右，向上跳，向右跳。它比較產生的成本，并選擇最小成本方向。

注意：這使用了通用的 unpack，在 python 3.5 中引入。但這不是必需的。

uj5u.com熱心網友回復：

下面是一個自下而上方法的例子，它似乎為這個例子和類似問題中的那個回傳了正確的結果。不過，我不確定代碼是否萬無一失。

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

標籤：Python 算法 调试 动态规划 分钟

上一篇：約瑟夫斯問題的負數解

下一篇：用于代數操作方程的編程語言