如何用動態規劃解決地形圖最短路徑？

Question

鑑於所有positive整數矩陣，從最左列0th出發，找到最右列(n - 1)th最小路徑。例如：

最小路徑是包含1的路徑。

在任何給定方m[i, j]，我們可以移動至4個方向（left, right, up, down）;當然除了最左邊，最右邊的所有行/列的所有角落案例。例如，在[0, 0]，我們只能移動right或down。
我的解決方案是建立一個m x n頂點圖，然後運行Floyd-Warshall來計算任意兩個頂點的所有最短路徑(u, v)。然後運行另一個嵌套循環for檢查與(n - 1)th列的所有頂點0th列的所有頂點找到最小路徑。
然而，我的教授通過以下復發建議另一種算法：

S[i, j, L] = 
    min(
     S[i - 1, j, L - 1] + cost[i - 1, j], 
     S[i + 1, j, L - 1] + cost[i + 1, j], 
     S[i, j - 1, L - 1] + cost[i, j - 1], 
     S[i, j + 1, L - 1] + cost[i, j + 1]); 

，我不知道它是如何工作！由於在任何給定的方形[i, j]我們可以在4個方向移動，這使得根據以前的預先計算的值建立一個表格是不可能的。
我在這裏錯過了什麼嗎？我看不出這種復發是如何發生的。任何想法？

Answer 1

如果有S [I，J，0] =無窮大，除了S [0，J，L] = 0，則它應該工作。最終所有的S [i，j，L] == S [i，j，L + 1]，你可以停止迭代。 S [i，j，L]則具有從第一列到該單元格的最短路徑的代價。

這是本復發會怎樣看在左上角增加L.

值

0 inf inf inf inf 
0 inf inf inf inf 
0 inf inf inf inf 

0 1 inf inf inf inf 
0 20 inf inf inf inf 
0 21 inf inf inf inf 

0 1 2 inf inf inf 
0 2 30 inf inf inf 
0 21 22 inf inf inf 

0 1 2 3 inf inf 
0 2 3 39 inf inf 
0 12 22 23 inf inf 

0 1 2 3 4 inf 
0 2 3 4 47 inf 
0 12 12 23 24 inf 

0 1 2 3 4 5 
0 2 3 4 5 48 
0 12 12 12 24 25 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 12 12 12 6 25 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 12 12 7 6 7 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 12 8 7 6 7 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 9 8 7 6 7 

沒有進一步的變化將發生在左上角。您可以看到它正在慢慢發現到達每個單元的最低成本。