64.最小路径和 (动态规划题)------力扣每日打卡Day4
1.题目
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
C语言函数头:
int minPathSum(int** grid, int gridSize, int* gridColSize){}
题目来源:力扣 戳我前往题目
2.题目分析
很明显,这道题是一道动态规划的题。做动态规划题最重要的就是:初始条件,迭代规律。
不妨设一个dp数组,和grid数组一样大,表示到dp[i][j]的最小值。也就是说,dp表示的是,前面的最小路径的和,表示一种状态。
如果对动态规划做法不是很理解的,可以先看一下我以前写的一道最简单的动态规划题 —— 爬楼梯。戳我前往爬楼梯题目
(1)初始条件
我们先看这题数组矩形的特点。蓝色部分就是数组,要从左上角的红色到右下角的红色的最小的路径。而且只能向下、向右移动。
如果移动到边缘的位置,绿色的地方dp[i][j]
的时候,因为只能向下向右,所以这个地方的dp只能是和旁边的或者上面的dp和grid加起来。
dp[0][0] = grid[0][0];
- 当 i= 0 的时候,
dp[i][j] = grid[i][j] + dp[i][j-1];
- 当 j = 0 的时候,
dp[i][j] = grid[i][j] + dp[i-1][j];
(2)迭代规律
通过上面的初始化规律应该也看出来了吧,dp[i][j]的值,就是最小路径和。因为只能通过向下向右,所以我们只要得到当前位置的,左边一步和上面一步的dp的最小值和当前位置的值相加,就能得出到当前位置的dp值,也就是到当前位置的最小路径和。
也就是说,如果要求到紫色块,只能从两个黄色块的位置到紫色块,找到两个值中的最小那个,再加上紫色块原本的值,就是紫色块的dp值,也就是最小路径。
所以,规律就是dp[i][j] = grid[i][j] + min(dp[i][j-1],dp[i-1][j]);
3.代码实现
//定义一个返回最小值的函数
int min(int a,int b){
return a > b? b:a;
}
int minPathSum(int** grid, int gridSize, int* gridColSize){
if(grid == NULL || gridSize == 0)
return 0;
int m = gridSize;
int n = gridColSize[0];
int dp[m][n];
dp[0][0] = grid[0][0];
//初始化dp数组
for(int i = 1; i < m; i++){
dp[i][0] = grid[i][0] + dp[i-1][0];
}
for(int i = 1; i < n; i++){
dp[0][i] = grid[0][i] + dp[0][i-1];
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
//动态规划的规律
dp[i][j] = grid[i][j] + min(dp[i][j-1],dp[i-1][j]);
}
}
return dp[m-1][n-1];
}
总结:
所以遇到动态规划题不要怕,找到初始条件,迭代规律,就是干!对dp[i][j]的理解也是很重要的,表示一种状态。
本文地址:https://blog.csdn.net/qq_46293423/article/details/107531219
上一篇: ES6数组解构 - Kaiqisan
下一篇: 零磁道受损的软盘格式化小技巧