我正在撰寫一個程式，從左下角到右上角遍歷網格，其中有效移動向右移動 1、向上移動 1 或向上或向右跳躍指定的數量跳躍陣列。輸入是二維陣列格式的網格、網格的維度：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，然后第二個塊跳轉到 (2, 2)，即是 1 所以 3 1 1 = 5. 如果 jumps 陣列只有 [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 的理解是什么，因為我剛剛學會了它），但這似乎只適用于某些輸入，我無法識別模式。
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]
我需要一些幫助來加速第一個或找出第二個有什么問題，或者可能獲得一些關于如何有效撰寫它的其他想法。謝謝
uj5u.com熱心網友回復：
在我看來，dp 應該有當前跳轉索引的另一個維度。一般來說，
dp[y][x][j] = 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] 作為 [row][column]，這在編程二維陣列訪問時很常見。）
uj5u.com熱心網友回復：
以下實作使用網格和剩余的跳轉作為狀態變數：
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只是為了簡化切片。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/321828.html