拼圖-nXn + ve，-ve整數網格。通過它查找最佳路徑

Question

您有一個包含一組正數和負數的NxN網格，並且您必須找到通過它的最佳路徑。路徑必須正好穿過每一行中的一個單元格，並且其相鄰行上的單元格必須垂直或對角地連接。你可以找到一個算法來解決這個問題，而不需要評估每個排列？

Answer 1

我假設「最佳路徑」被定義爲最高總和的路徑？

您可以使用動態編程。對於每一行，將該行的元素設置爲結束於該行的最佳路徑值。所以

solution[i][j] = grid[i][j] + max(solution[i-1][j], solution[i-1][j-1], solution[i-1][j+1]) 

當然考慮到邊界條件。初始條件爲：

solution[0][j] = grid[0][j] 

您還需要跟蹤最佳路徑所採用的實際路徑（選擇哪個網格元素）。一旦到達最後一行，通過該行並找到最大值。這會給你最佳的路徑和價值。