最小路径和
- 1.题目
- 2.题目分析
- (1)初始条件
- (2)迭代规律
- 3.代码实现
- 总结:
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]的理解也是很重要的,表示一种状态。
c/c++开发分享64.最小路径和 (动态规划题)——力扣每日打卡Day4地址:https://blog.csdn.net/qq_46293423/article/details/107531219
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598544.html