leetcode算法题--最小路径和

原题链接：https://leetcode-cn.com/problems/minimum-path-sum/

相关题目：不同路径

动态规划：

dp[i][j]表示走到(i,j)点的最小路径和

状态转移：

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];

代码：

int minPathSum(vector<vector<int>>& grid) { int m,n; m=grid.size(); n=grid[0].size(); vector<vector<int>> dp(m,vector<int>(n)); dp[0][0]=grid[0][0]; //初始化dp第一列 for(int i=1;i<m;i++) { dp[i][0]=dp[i-1][0]+grid[i][0]; } //初始化dp第一行 for(int i=1;i<n;i++) { dp[0][i]=dp[0][i-1]+grid[0][i]; } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } return dp[m-1][n-1]; }