c/c++语言开发共享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]的理解也是很重要的，表示一种状态。

c/c++开发分享64.最小路径和 （动态规划题）——力扣每日打卡Day4地址：https://blog.csdn.net/qq_46293423/article/details/107531219