java数据结构与算法刷题-----LeetCode64. 最小路径和

发布时间:2024年01月07日
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只不过大家都叫它dp),达到空间换时间的效果。它仅仅只是一种优化思路,因此它目前的境地和线性代数一样----虚假的难。

  1. 想想线性代数,在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时,完全摸不着头脑,一上来就是行列式和矩阵,根本不知道这玩意是干嘛的。
  2. 线性代数从根本上是在空间上研究向量,抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。
  3. 反观国内的教材,直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候,只会觉得一知半解,觉得麻烦,完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候,发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材,什么狗东西(以上是自己学完线性代数后的吐槽,我们同学无一例外都这么觉得)。

而我想告诉你,动态规划和线性代数一样,我学完了才知道,它不过就是研究空间换时间,提前将固定的重复操作规划到dp数组中,而不用暴力求解,从而让效率极大提升。

  1. 但是网上教动态规划的兄弟们,你直接给一个动态方程是怎么回事?和线性代数,一上来就教行列式和矩阵一样,纯属恶心人。我差不多做了30多道动态规划题目,才理解,动态方程只是一个步骤而已,而这已经浪费我很长时间了,我每道题都一知半解不理解,过程及其痛苦。最后只能重新做。
  2. 动态规划,一定是优先考虑重复操作与dp数组之间的关系,搞清楚后,再提出动态方程。而你们前面步骤省略了不讲,一上来给个方程,不是纯属扯淡吗?
  3. 我推荐研究动态规划题目,按5个步骤,从上到下依次来分析
  1. DP数组及下标含义
  2. 递推公式
  3. dp数组初始化
  4. 数组遍历顺序(双重循环及以上时,才考虑)
  5. dp数组打印,分析思路是否正确(相当于做完题,检查一下)

在这里插入图片描述

这道题是62题的衍生题,在62题的基础上,增加了一个条件,就是每个方块都有一个开销值,我们需要选择开销最小的哪条路,除此之外没有任何区别

可以先参考🏆LeetCode62. 不同路径https://blog.csdn.net/grd_java/article/details/135421514
先理解题目细节

在这里插入图片描述

  1. 起点在[0,0]位置,且只能向右或向下走,也就是说,我们到达每一个方格,只有两种情况,从上面过来的,或者从左面过来的。注意区分“走过去”和“从哪过来的区别”,这是解出这道题的关键。
  2. 我们依次走到每一个方块,不管其它的,只看当前方块,研究当前方块的最短路径
  3. 步骤如下:
  1. [0,0]位置:开销是1,到达这个位置只有一种方法,直接站上去,所以最短路径的开销就是1,故dp[0,0] = 1
  2. 第一行除起点[0,0]外的方块,想要到达它们同样只有一条路,那就是从起点一直向右走
  1. [0,1]位置,其本身开销为3,只有一种方法可以到达它,就是从左边过来,所以加上从起点到达左边这个[0,0]位置的最短开销1,一共为4. 因此 dp[0,1] = 4
  2. 同理[0,2]位置,本身开销1+起点到左边位置[0,1]开销4 = 5,故dp[0,2] = 5
  1. 第一列和第一行同理,除[0,0]外,只有从起点往下走这一条路
  1. [1,0]位置开销 = 本身开销1+[0,0]位置开销1 = 2
  2. **[2,0]位置开销 = 本身开销4+起点到[1,0]的开销 2=6 **
  1. 其余位置都有两种情况,从左边过来,或者从上面过来。因为这道题求最短开销,因此两个方向选小的那个
  1. [1,1]位置 = min{本身开销5+左边[1,0]开销2 = 7 , 本身开销5+ 上面[0,1]开销4 = 9} = 7. 从左边过来开销为7,上面过来开销为9,选小的7。
  2. [1,2]位置 = min{本身开销1+左边[1,1]开销7 = 8 , 本身开销1+ 上面[0,2]开销5 = 6} = 6
  3. [2,1]位置 = min{本身开销2+左边[2,0]开销6 = 8 , 本身开销2+ 上面[1,1]开销7 = 9} = 8
  4. [2,2]位置 = min{本身开销1+左边[2,1]开销8 = 9 , 本身开销1+ 上面[1,2]开销6 = 7} = 7
  1. 构建完dp数组,我们要返回的是起点[0,0]到终点[2,2]的最短路径,他就保存在dp[2,2]中。因为我们dp数组存储的就是起点到达每个位置的最短开销。
解题思路
  1. 暴力求解的思想,就是回溯算法,枚举每一种情况,拿到最大值,显然会做大量无效运算。
  2. 但是如果我们预先将其存储到dp数组,就可以直接通过dp[x], 获取dp数组中指定位置x的体力花费,而不用枚举。典型的动态规划题目
动态规划思考5步曲
  1. DP数组及下标含义

我们要求出的是到达某个方块,可以从哪里过来,过来的几种方法谁的开销最小,那么dp数组中存储的就是到达这里的最短路径开销。要求出谁的从起点到达后的最短开销呢?显然是某个方块,那么下标就是代表现在到了哪个方块,也就是代表到了某一方块后的最短开销。显然,需要2个下标表示,故这道题的dp数组需要二维数组

  1. 递推公式
  1. 由题意可知,只能选择向右走或者向下走,因此对于每个方块而言,只能是从上面过来,或者从左面过来。而第一行没有从上面来的路,因此只能从左面过来,也就是第一行都只有一条从左面来的路,直接计算从起点到它的开销即可。同理第一列,没有从左面来的路,只能从上面过来,也只有从上面过来这一条路,计算从起点到它的开销即可。
  1. 起点[0,0]的开销固定为其本身开销。F(0,0) = 其本身开销
  2. 第一行和第一列都固定为其唯一可通的路上的开销(行:从起点一直向右走。列是从起点一直向下走),F(0,n) = F(0,n-1)+其本身开销; F(n,0) = F(n-1,0)+其本身开销
  1. 之后每一个方块,都需要考虑从上面来的路,和从左面来的路。也就是到它上面的方块最短路径开销+其本身开销。和到它左面的方块的最短开销+其本身开销。选一个小的。
  2. 因此,可以得到,从第二行,第二列开始,递推公式变为,min(到左边方块的最短开销+其本身开销,到上面方块的最短开销+其本身开销)。F(n,n) = min(F(n-1,n)+其本身开销,F(n,n-1)+其本身开销)
  1. dp数组初始化

在这里插入图片描述

  1. 数组遍历顺序

双重循环,我们知道这道题,数组下标表示方块的位置,也就是所在行和列的位置。那么其中一层循环代表第几行,另外一层循环代表第几列。那么先遍历行还是列呢?我们发现,无论遍历哪个,都不影响。我们可以一列一列考虑,也可以一行一行考虑,因此,先遍历哪个都一样。我们这里选择先遍历行。

  1. 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)

在这里插入图片描述

代码:时间复杂度O(mn).空间复杂度O(mn)

在这里插入图片描述

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length,n = grid[0].length;//获取行和列
        int dp[][] = new int[m][n];//dp数组表示每个方块,每个元素值代表从起点到这个方块的最短路径,下标代表其所在行和列
        dp[0][0] = grid[0][0];//到达第一个方块,只有一种方法,就是直接站上去,所以最短路径就是它本身开销
        //对于第一列来说,只有从上往下走这一条路,因此这条路上的每个方块的开销,就是从起点沿着这条路走到它的开销
        for(int i = 1;i<m;i++) dp[i][0] = dp[i-1][0]+grid[i][0];
        //第一行同理,只有从左往右这一条路
        for(int j = 1;j<n;j++) dp[0][j] = dp[0][j-1]+grid[0][j];
        //剩余的每个方块,都可以从上面过来,也可以从左面过来,我们选择值小的,也就是路径开销小的方向
        for(int i = 1;i<m;i++)
            for(int j = 1;j<n;j++)
                    dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
        return dp[m-1][n-1];//最后返回终点的最短路径开销
    }
}
文章来源:https://blog.csdn.net/grd_java/article/details/135430626
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。