题目链接:leetcode最小路径和
目录
题目让我们求从左上角到右下角的路径,使得路径上的数字总和为最小
由题可得:
每次只能向下或者向右移动一步
先创建一个dp表
首先先思考dp表里面的值所表示的含义(是什么?)
dp[i][j]表示到达[i][j]路径上的数字总和为最小
这种状态表示怎么来的?
1.经验+题目要求
用之前或者之后的状态,推导出dp[i][j]的值;
根据最近的最近的一步,来划分问题
经验:以i位置为结尾
题目让我们求到达右下角路径上的数字总和为最小,那么这里我们可以dp[i][j]来表示。
所以这里我们用i*j表示右下角位置;
dp[i]等于什么?
因为我们每次只能向下或者向右移动一步
所以到达[i][j]位置有两种情况:
第一种:从[i-1][j]到达i位置
我们这里只要知道到达[i-1][j]路径上的数字总和的最小值,再加上[i]位置的数值(grid[i][j])
就可以得到[i][j]位置路径上的数字总和的最小值(dp[i][j]);
而“到达[i-1][j]路径上的数字总和的最小值”正好是我们的状态表示:dp[i-1][j]
所以这一种情况的状态转移方程为:
dp[i]=dp[i-1][j]+grid[i][j]
第二种:从[i-1][j]到达i位置
我们这里只要知道到达[i][j-1]路径上的数字总和的最小值,再加上[i]位置的数值(grid[i][j])
就可以得到[i][j]位置路径上的数字总和的最小值(dp[i][j]);
而“到达[i][j-1]路径上的数字总和的最小值”正好是我们的状态表示:dp[i][j-1]
所以这一种情况的状态转移方程为:
dp[i]=dp[i][j-1]+grid[i][j]
总结这两种情况:
因为题目让我们求的是到达右下角路径上的数字总和为最小
所以这里我们要取这两种情况的最小值
dp[i][j]=min(dp[i-1][j]+dp[i][j-1])+grid[i][j]
(保证填表的时候不越界)
由我们的状态转移方程得:
在0行0列的时候越界,所以我们这里可以在m*n的外围多加1行1列,如图:
还有一个问题是:
我们要拿新增用来初始化的行和列要初始化为几呢?
这里我们需要注意的一点就是在dp[1][1]的时候,路径上的数字总和的最小值就是他本身grid
所以我们只要在dp表里的dp[0][1]、dp[1][0]中任选一个
初始化为cost[0][0]就可以了
其他的地方直接初始化为无穷大值INT_MAX
(为了填写当前状态的时候,所需要的状态已经计算过了)
这里所需要的状态是:到达该位置的上面和左边位置的方式
所以填表顺序:
从上到下填写每一行
从左到右填写每一列
(根据题目要求和状态表示)
综上分析:
返回值为:dp[m][n];
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
//1.创建dp表
//2.初始化
//3.填表
//4.返回结果
int m=grid.size();
int 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+1;i++)
for(int j=1;j<n+1;j++)
dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];
return dp[m][n];
}
};