動態規劃m * n網格最短sumpath

Question

我正在學習一些算法和DS，並且遇到了DP問題。尋找一些提示。這裏是聲明：

給定一個mxn網格填充非負數，找到一個從左上角到右下角的路徑，它將沿着路徑的所有數字的總和最小化。

注意：您只能在任何時間點向下或向右移動。

提示只請！

我想過一些事情，但他們只是不工作。它沒有意義，因爲我最初的想法是，

用dp [i] [j]記憶其中dp [i] [j]是i * j網格的最小路徑和。這是沒有道理的，因爲我例如不知道如何從中得到[i + 1] [j + 1]。

這個想法是否正確。你能提出一些建議嗎？

Answer 1

這看起來像是「迪克斯特拉的最短路徑」問題。 您可以使用矩陣 創建圖形，然後應用Dijkstra的最短路徑算法來解決此問題。 以（0,0）作爲你的初始頂點和（m-1，n-1）作爲你的最終頂點;

例子：

matrix of 3x3 is: 
0 0 3 
5 0 3 
0 3 0 

and graph is: 
i f w 
------ 
0->0 0 
0->1 0 
0->2 3 
1->0 5 
1->1 0 
1->2 3 
2->0 0 
2->1 3 
2->2 0 

here i => initial 
    f => final 
    w => weight 

並立即申請了Dijkstra的最短路徑算法。

Answer 2

初始化角單元，即dp[0][j]和dp[i][0]。然後，對於任何dp[i][j]，遍歷到該路徑的成本將爲val[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])。

dp[row][col]應該有最小路徑的代價。您也可以使用dp[][]回溯，並找到最低成本路徑。

祝你好運。