如何用动态规划解决地形图最短路径？

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 

没有进一步的变化将发生在左上角。您可以看到它正在慢慢发现到达每个单元的最低成本。