动态规划_最小路径和_C++

一.题目解析

算法解析

1.状态表示

dp[i][j]表示到(i,j)位置的最小和

2.状态转换方程

3.初始化

我们在边界上添加了一行一列所以我们想要找到原矩阵的值就需要横纵坐标减去1,即需要注意下标的映射,这是比较容易忽略的点.

4.填表顺序

从上到下

5.返回值

dp[m][n]

二.代码实现

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));
dp[0][1]=0;
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-1][j-1];//注意正确的映射
return dp[m][n];
}
};