[dp]leetcode64：最小路径和(medium)

路径和(medium)"/>

[dp]leetcode64：最小路径和(medium)

题目：

题解：

• 本题是动态规划的经典好题，状态方程也比较简单。
• dp[i][j]表示原点坐标达到点[i,j]的最小路径和权值，状态转移方程：dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];

代码如下：

class Solution {
public://题解：动态规划，dp[i][j]表示到达点[i,j]的最小路径和//注意这题不是贪心算法，因为这里取左上两点的最小值是全局最优的，不是局部最优的int minPathSum(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();int dp[n][m];memset(dp,0,sizeof(dp));dp[0][0]=grid[0][0];for(int i=1;i<n;++i){//处理第一列的路径权值和dp[i][0]=dp[i-1][0]+grid[i][0];}for(int i=1;i<m;++i){//处理第一行的路径权值和dp[0][i]=dp[0][i-1]+grid[0][i];}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])+grid[i][j];}}return dp[n-1][m-1];}
};