Given a?m?x?n?grid filled with non-negative numbers, find a path from top left to bottom right which?minimizes?the sum of all numbers along its path.

Note:?You can only move either down or right at any point in time.

---

典型的動態(tài)規(guī)劃問題。

設(shè)dp[i][j]表示從左上角到grid[i][j]的最小路徑和。那么dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] );

下面的代碼中，為了處理計算第一行和第一列的邊界條件，我們令dp[i][j]表示從左上角到grid[i-1][j-1]的最小路徑和，最后dp[m][n]是我們所求的結(jié)果

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class?Solution { public: ????int?minPathSum(vector<vector<int> > &grid) { ????????int?row = grid.size(),col; ????????if(row == 0)return?0; ????????else?col = grid[0].size(); ????????vector<vector<int> >dp(row+1, vector<int>(col+1, INT_MAX)); ????????dp[0][1] = 0; ????????for(int?i = 1; i <= row; i++) ????????????for(int?j = 1; j <= col; j++) ????????????????dp[i][j] = grid[i-1][j-1] + min(dp[i][j-1], dp[i-1][j]); ????????return?dp[row][col]; ????} };

?

注意到上面的代碼中dp[i][j] 只和上一行的dp[i-1][j]和上一列的dp[i][j-1]有關(guān)，因此可以優(yōu)化空間為O（n）（準確來講空間復(fù)雜度可以是O（min（row,col

）））??????????????????????????本文地址

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class?Solution { public: ????int?minPathSum(vector<vector<int> > &grid) { ????????int?row = grid.size(),col; ????????if(row == 0)return?0; ????????else?col = grid[0].size(); ????????vector<int?>dp(col+1, INT_MAX); ????????dp[1] = 0; ????????for(int?i = 1; i <= row; i++) ????????????for(int?j = 1; j <= col; j++) ????????????????dp[j] = grid[i-1][j-1] + min(dp[j], dp[j-1]); ????????return?dp[col]; ????} };

---

問題擴展

最大路徑和只需要把上面的遞推公式中的min換成max。

現(xiàn)在有個問題，如果兩個人同時從左上角出發(fā)，目的地是右下角，兩個人的路線不能相交（即除了出發(fā)點和終點外，兩個人不同通過同一個格子），使得兩條路徑的和最大。（這和一個人先從左上角到右下角，再回到左上角是相同的問題）。

這是雙線程動態(tài)規(guī)劃問題：假設(shè)網(wǎng)格為grid，dp[k][i][j]表示兩個人都走了k步，第一個人向右走了i步，第二個人向右走了j步 時的最大路徑和（只需要三個變量就可以定位出兩個人的位置grid[k-i][i-1] 、 grid[k-j][j-1]），那么

dp[k][i][j] = max(dp[k-1][i-1][j-1], dp[k-1][i][j], dp[k-1][i-1][j], dp[k-1][i][j-1]) + grid[k-i][i-1] + grid[k-j][j-1]? （我們假設(shè)在起始位置時就已經(jīng)走了一步）

?

這個方程的意思是從第k-1步到第k步，可以兩個人都向右走、都向下走、第一個向下第二個向右、第一個向右第二個向下，這四種走法中選擇上一步中路徑和最大的。

?

由于要保證兩條路線不能相交，即兩個人走的過程中，有一個人向右走的步數(shù)永遠大于另一個人向右走的步數(shù)，我們不妨設(shè)第二個人向右走的步數(shù)較大，即dp[k][i][j]中j > i才是有效的狀態(tài)。走到終點的步數(shù)為：網(wǎng)格的行數(shù)+網(wǎng)格的列數(shù)-1

?

需要注意的是：當走了k步時，某個人向右走的步數(shù)必須 > k - 網(wǎng)格的行數(shù)，如果向右走的步數(shù) <= k-行數(shù)，那么向下走的步數(shù) = k-向右走的步數(shù) >= 行數(shù)，此時超出了網(wǎng)格的范圍。由于我們假設(shè)了 j > i,因此只要保證 i > k-網(wǎng)格行數(shù)即可。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int?max2PathSum(vector<vector<int> > grid) { ????int?row = grid.size(), col = grid[0].size(); ????vector<vector<vector<int> > > dp(row+col, vector<vector<int> >(col+1, vector<int>(col+1, 0))); ????for(int?step = 2; step <= row+col-2; step++) ????????for(int?i = max(1, step-row+1); i <= step && i <= col; i++) ????????????for(int?j = i+1; j <= step && j <= col; j++) ????????????{ ????????????????? ????????????????dp[step][i][j] = max(max(dp[step-1][i][j], dp[step-1][i-1][j-1]), max(dp[step-1][i-1][j], dp[step-1][i][j-1])); ????????????????dp[step][i][j] += (grid[step-i][i-1] + grid[step-j][j-1]); ????????????} ????return?dp[row+col-2][col-1][col] + 2*grid[row-1][col-1] + 2*grid[0][0]; }

?

我們最終的目標是dp[row+col-1][col][col] = max{dp[row+col-2][col-1][col-1], dp[row+col-2][col][col], dp[row+col-2][col-1][col], dp[row+col-2][col][col-1]} + 2*grid[row-1][col-1]

由于dp[row+col-2][col-1][col-1], dp[row+col-2][col][col], dp[row+col-2][col][col-1]都是無效的狀態(tài)（dp[k][i][j]中j > i才是有效的狀態(tài)），

所以dp[row+col-1][col][col]? = dp[row+col-2][col-1][col] + 2*grid[row-1][col-1]，代碼中最后結(jié)果還加上了所在起點的的網(wǎng)格值。

由以上可知，循環(huán)中最多只需要求到了dp[row+col-2][][]。

?

nyoj中?傳紙條（一）就是這個問題，可以在這一題中測試上述函數(shù)的正確性，測試代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int?main() { ????int?n; ????scanf("%d",&n); ????for(int?i = 1; i <= n; i++) ????{ ????????int?row, col; ????????scanf("%d%d", &row, &col); ????????vector<vector<int> >grid(row, vector<int>(col)); ????????for(int?a = 0; a < row; a++) ????????????for(int?b = 0; b < col; b++) ????????????????scanf("%d", &grid[a][b]); ????????printf("%d\n", max2PathSum(grid)); ????} ????return?0; }

?

這個問題還可以使用最小費用流來解決，具體可以參考here

?

本文轉(zhuǎn)自tenos博客園博客，原文鏈接：http://www.cnblogs.com/TenosDoIt/p/3774804.html，如需轉(zhuǎn)載請自行聯(lián)系原作者

總結(jié)

以上是生活随笔為你收集整理的LeetCode:Minimum Path Sum（网格最大路径和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。