? ? ? ? 題目：給定一個包含非負整數的 m x n 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小，每次只能向下或者向右移動一步

輸入: [[1,3,1],[1,5,1],[4,2,1] ] 輸出: 7 解釋: 因為路徑 1→3→1→1→1 的總和最小。

先給出動態規劃方程：dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]

求左上到右下的最小路徑和，看來又一個累加問題，可以從局部最小和到整體最小和。為了方便說明，我們對矩陣進行標號，左上角對于[0][0]位，右下角對應[2][2]位。到達[2][2]位可以從[1][2]或[2][1]到達，這就轉化為從[0][0]到[1][2]和從[0][0]到[2][1]中取最小值。下面給出代碼：

?

#include<iostream> #include<vector> using namespace std;void printSum(vector<vector<long long>> sum) {for(int k=0;k<3;k++){ for(int z=0;z<3;z++){cout << sum[k][z] << ",";}cout << endl;} }int minPathSum(vector<vector<int>>& grid) {int n=grid.size(); //這個vector里有幾個vector元素int m=grid[0].size(); //vector里面的vector大小vector<vector<long long>> sum(n,vector<long long>(m,0));int i,j;sum[0][0] = grid[0][0];//左上角for(i=1; i<n; i++)//縱向求和{sum[i][0] = sum[i-1][0]+grid[i][0];}for(j=1; j<m; j++)//橫向求和{sum[0][j] = sum[0][j-1]+grid[0][j];}//n表示縱向，m表示橫向for(i=1; i<n; i++){for(j=1; j<m; j++){cout << "-------sum" << endl;printSum(sum);cout << "-----------------detail" << endl;cout << "grid[i][j]=" << grid[i][j] << endl;cout << "min=" << min(sum[i-1][j],sum[i][j-1]) << endl;sum[i][j] = grid[i][j]+min(sum[i-1][j],sum[i][j-1]);}cout << "*******************************" << endl;}return sum[i-1][j-1]; }int main(){vector<vector<int>> v={{1,3,1},{1,5,1},{4,2,1}}; int n = minPathSum(v);cout<< "n=" << n << endl; }

?運行結果：

-------sum
1,4,5,
2,0,0,
6,0,0,
-----------------detail
grid[i][j]=5
min=2
-------sum
1,4,5,
2,7,0,
6,0,0,
-----------------detail
grid[i][j]=1
min=5
*******************************
-------sum
1,4,5,
2,7,6,
6,0,0,
-----------------detail
grid[i][j]=2
min=6
-------sum
1,4,5,
2,7,6,
6,8,0,
-----------------detail
grid[i][j]=1
min=6
*******************************
n=7

sum用來存儲從[0][0]到sum[i][j]路徑的最小和,看看每次sum的變化,sum[1][1] = 7表明從[0][0]到[1][1]路徑最小和是7，程序先把第2行對于的sum都求出來，再把第2列對應的sum都求出來，最后求sum[2][2]就很容易了。

??

?參考地址：https://blog.csdn.net/weixin_43750513/article/details/106738099

總結

以上是生活随笔為你收集整理的动态规划算法--矩形最小路径和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。