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