电影网站怎么做,网站后台 搜索,加强网站信息建设管理,做网站刷流量挣钱吗java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难#xff0c;但它就是固定套路而已。其实动态规划只…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难但它就是固定套路而已。其实动态规划只不过是将多余的步骤提前放到dp数组中就是一个数组只不过大家都叫它dp达到空间换时间的效果。它仅仅只是一种优化思路因此它目前的境地和线性代数一样----虚假的难。 想想线性代数在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时完全摸不着头脑一上来就是行列式和矩阵根本不知道这玩意是干嘛的。线性代数从根本上是在空间上研究向量抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。反观国内的教材直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候只会觉得一知半解觉得麻烦完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材什么狗东西以上是自己学完线性代数后的吐槽我们同学无一例外都这么觉得。 而我想告诉你动态规划和线性代数一样我学完了才知道它不过就是研究空间换时间提前将固定的重复操作规划到dp数组中而不用暴力求解从而让效率极大提升。 但是网上教动态规划的兄弟们你直接给一个动态方程是怎么回事和线性代数一上来就教行列式和矩阵一样纯属恶心人。我差不多做了30多道动态规划题目才理解动态方程只是一个步骤而已而这已经浪费我很长时间了我每道题都一知半解不理解过程及其痛苦。最后只能重新做。动态规划一定是优先考虑重复操作与dp数组之间的关系搞清楚后再提出动态方程。而你们前面步骤省略了不讲一上来给个方程不是纯属扯淡吗我推荐研究动态规划题目按5个步骤从上到下依次来分析 DP数组及下标含义递推公式dp数组初始化数组遍历顺序双重循环及以上时才考虑dp数组打印分析思路是否正确相当于做完题检查一下 这道题是62题的衍生题在62题的基础上增加了一个条件就是每个方块都有一个开销值我们需要选择开销最小的哪条路除此之外没有任何区别 可以先参考LeetCode62. 不同路径https://blog.csdn.net/grd_java/article/details/135421514
先理解题目细节 起点在[0,0]位置且只能向右或向下走也就是说我们到达每一个方格只有两种情况从上面过来的或者从左面过来的。注意区分“走过去”和“从哪过来的区别”这是解出这道题的关键。我们依次走到每一个方块不管其它的只看当前方块研究当前方块的最短路径步骤如下 [0,0]位置开销是1到达这个位置只有一种方法直接站上去所以最短路径的开销就是1故dp[0,0] 1第一行除起点[0,0]外的方块想要到达它们同样只有一条路那就是从起点一直向右走 [0,1]位置其本身开销为3只有一种方法可以到达它就是从左边过来所以加上从起点到达左边这个[0,0]位置的最短开销1一共为4. 因此 dp[0,1] 4同理[0,2]位置本身开销1起点到左边位置[0,1]开销4 5故dp[0,2] 5 第一列和第一行同理除[0,0]外只有从起点往下走这一条路 [1,0]位置开销 本身开销1[0,0]位置开销1 2**[2,0]位置开销 本身开销4起点到[1,0]的开销 26 ** 其余位置都有两种情况从左边过来或者从上面过来。因为这道题求最短开销因此两个方向选小的那个 [1,1]位置 min{本身开销5左边[1,0]开销2 7 本身开销5 上面[0,1]开销4 9} 7. 从左边过来开销为7上面过来开销为9选小的7。[1,2]位置 min{本身开销1左边[1,1]开销7 8 本身开销1 上面[0,2]开销5 6} 6[2,1]位置 min{本身开销2左边[2,0]开销6 8 本身开销2 上面[1,1]开销7 9} 8[2,2]位置 min{本身开销1左边[2,1]开销8 9 本身开销1 上面[1,2]开销6 7} 7 构建完dp数组我们要返回的是起点[0,0]到终点[2,2]的最短路径他就保存在dp[2,2]中。因为我们dp数组存储的就是起点到达每个位置的最短开销。 解题思路 暴力求解的思想就是回溯算法枚举每一种情况拿到最大值显然会做大量无效运算。但是如果我们预先将其存储到dp数组就可以直接通过dp[x], 获取dp数组中指定位置x的体力花费而不用枚举。典型的动态规划题目 动态规划思考5步曲 DP数组及下标含义 我们要求出的是到达某个方块可以从哪里过来过来的几种方法谁的开销最小那么dp数组中存储的就是到达这里的最短路径开销。要求出谁的从起点到达后的最短开销呢显然是某个方块那么下标就是代表现在到了哪个方块也就是代表到了某一方块后的最短开销。显然需要2个下标表示故这道题的dp数组需要二维数组 递推公式 由题意可知只能选择向右走或者向下走因此对于每个方块而言只能是从上面过来或者从左面过来。而第一行没有从上面来的路因此只能从左面过来也就是第一行都只有一条从左面来的路直接计算从起点到它的开销即可。同理第一列没有从左面来的路只能从上面过来也只有从上面过来这一条路计算从起点到它的开销即可。 起点[0,0]的开销固定为其本身开销。F(0,0) 其本身开销第一行和第一列都固定为其唯一可通的路上的开销行从起点一直向右走。列是从起点一直向下走F(0,n) F(0,n-1)其本身开销; F(n,0) F(n-1,0)其本身开销 之后每一个方块都需要考虑从上面来的路和从左面来的路。也就是到它上面的方块最短路径开销其本身开销。和到它左面的方块的最短开销其本身开销。选一个小的。因此可以得到从第二行第二列开始递推公式变为min(到左边方块的最短开销其本身开销到上面方块的最短开销其本身开销)。F(n,n) minF(n-1,n)其本身开销F(n,n-1)其本身开销 dp数组初始化 数组遍历顺序 双重循环我们知道这道题数组下标表示方块的位置也就是所在行和列的位置。那么其中一层循环代表第几行另外一层循环代表第几列。那么先遍历行还是列呢我们发现无论遍历哪个都不影响。我们可以一列一列考虑也可以一行一行考虑因此先遍历哪个都一样。我们这里选择先遍历行。 打印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;im;i) dp[i][0] dp[i-1][0]grid[i][0];//第一行同理只有从左往右这一条路for(int j 1;jn;j) dp[0][j] dp[0][j-1]grid[0][j];//剩余的每个方块都可以从上面过来也可以从左面过来我们选择值小的也就是路径开销小的方向for(int i 1;im;i)for(int j 1;jn;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];//最后返回终点的最短路径开销}
}
