如何建设一个简易网站/天津网站优化软件

矩阵的最小路径和：动态规划思想。

生成大小和输入矩阵matrix一样大小的矩阵dp，dp[i][j]表示从左上角（0，0）位置走到（i，j）位置的最小路径和，当i=n-1，j=m-1时，dp[i][j]就是矩阵的最小路径和。

首先对于第一行（n=0），到达每一列的位置只能由前一列位置水平走过去（因为规定只能向右或向下走）；对于第一列（m=0），到达每一行的位置只能由前一行位置垂直走过去；所以我们要单独处理dp[0][j]（到达第一行的每一列位置的最小路径和，即当前位置的值matrix[0][j]加上前j-1列的最小路径和dp[0][j-1]）以及单独处理dp[i][0]（到达第一列的每一行位置的最小路径和，即当前位置的值matrix[i][0]加上前i-1行的最小路径和dp[i-1][0]）。

然后两层for循环，得到到达每一个位置的最小路径和dp[i][j]；最后返回dp[n-1][m-1]的值，即为矩阵的最小路径和（走到了右下角）。

代码如下：

class Solution {
public:int minPathSum(vector<vector<int> >& matrix) {// write code hereif(matrix.size()==0) return 0;int n=matrix.size();int m=matrix[0].size();vector<vector<int>> dp(n,vector<int>(m,0));dp[0][0]=matrix[0][0];for(int j=1;j<m;j++)dp[0][j]=dp[0][j-1]+matrix[0][j];for(int i=1;i<n;i++)dp[i][0]=dp[i-1][0]+matrix[i][0];for(int i=1;i<n;i++){for(int j=1;j<m;j++){dp[i][j]=min(dp[i][j-1],dp[i-1][j])+matrix[i][j];}}return dp[n-1][m-1];}
};