欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

64.最小路径和 (动态规划题)------力扣每日打卡Day4

程序员文章站 2022-03-22 10:02:25
最小路径和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* gridCol...

1.题目

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 13111 的总和最小。

C语言函数头:

int minPathSum(int** grid, int gridSize, int* gridColSize){}

题目来源:力扣 戳我前往题目

2.题目分析

很明显,这道题是一道动态规划的题。做动态规划题最重要的就是:初始条件,迭代规律。
不妨设一个dp数组,和grid数组一样大,表示到dp[i][j]的最小值。也就是说,dp表示的是,前面的最小路径的和,表示一种状态。
如果对动态规划做法不是很理解的,可以先看一下我以前写的一道最简单的动态规划题 —— 爬楼梯。戳我前往爬楼梯题目

(1)初始条件

我们先看这题数组矩形的特点。蓝色部分就是数组,要从左上角的红色到右下角的红色的最小的路径。而且只能向下、向右移动
64.最小路径和 (动态规划题)------力扣每日打卡Day4

如果移动到边缘的位置,绿色的地方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];

64.最小路径和 (动态规划题)------力扣每日打卡Day4

(2)迭代规律

通过上面的初始化规律应该也看出来了吧,dp[i][j]的值,就是最小路径和。因为只能通过向下向右,所以我们只要得到当前位置的,左边一步和上面一步的dp的最小值和当前位置的值相加,就能得出到当前位置的dp值,也就是到当前位置的最小路径和。

也就是说,如果要求到紫色块,只能从两个黄色块的位置到紫色块,找到两个值中的最小那个,再加上紫色块原本的值,就是紫色块的dp值,也就是最小路径。
64.最小路径和 (动态规划题)------力扣每日打卡Day4
所以,规律就是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

相关标签: 算法题