【代码随想录训练营】【Day39】第九章|动态规划|62.不同路径|63. 不同路径 II
创始人
2024-06-01 11:35:06
0

不同路径

题目详细:LeetCode.62

有点简单呀,做类似这种题型时,最好就是先画图:

  • 可以像题目一样,画一个二维表格,表格内的值代表到达这个格子的不同路径总数
  • 那么已知,如果图的大小为m == 1 || n == 1时,即只有一列或一行时,那么其不同路径总数都只有一条
  • 当出现其他情况时,我们并不难发现格子内的数值刚好等于其上边和左边格子的和,即其不同路径总数为经过上边和左边格子的不同路径之和
  • 那么我们以此规律就可以依次计算出除第一列和第一行外,到达其他各个格子的不同路径数目
  • 最后我们即可得到右下角终点的值,即为到达终点的不同路径总数

详细的解题思路我都写在注释里了,也可查阅:《代码随想录》— 不同路径

Java解法(动态规划):

class Solution {public int uniquePaths(int m, int n) {// 只有一列或一行时,那么其不同路径总数都只有一条if(m == 1 || n == 1){return 1;}// 主要初始化第一行和第一列的不同路径数都为1int[][] map = new int[m][n];for(int i = 0; i < m; i++){Arrays.fill(map[i], 1);}// 动态规划:从左往右,从上往下,计算到达每一个格子的不同路径总数for(int i = 1, j = 1; i < m;){// 递推公式map[i][j] = map[i - 1][j] + map[i][j - 1];// 先从左往右j++;if(j == n){// 到达右边界后,初始化列的下标j = 1;// 从上往下i++;}}return map[m - 1][n - 1];}
}

不同路径 II

题目详细:LeetCode.63

与上一题的区别在于这道题增加了障碍物,不过思路也不难,只要注意以下几点:

  • 如果起点或终点出现了障碍物,则最终的不同路径总数都为0
  • 对于第一列和第一行的初始化,按照从左往右,从上往下的顺序依次初始化为1,如果路径中出现了障碍物,则说明此路不通,后续的格子都初始化为0
  • 将有障碍物的格子的不同路径总数记作0,只有遇到无障碍物的格子才累计其不同路径数目

那么只要根据以上三点,进行相对应的逻辑处理即可,累计格子的不同路径数目的思路与上一题的思路无异,详细的解题思路我都写在注释里了,也可查阅:《代码随想录》— 不同路径 II

Java解法(动态规划):

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length, n = obstacleGrid[0].length;// 特判,当障碍物出现在终点或起点时,不同路径总数都为0if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1){return 0;}// 定义一个辅助二维数组dp,防止直接操作原数组时,出现obstacleGrid[i][j] == 1的情况,将障碍物的表示数值累加进路径总数中int[][] dp = new int[m][n];// 对第一列和第一行进行赋值,路径总数为1,但是当路线上出现障碍物时,其后续的格子的路径总数都为0for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){dp[i][0] = 1;}for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++){dp[0][j] = 1;}// 从左往右,从上往下记录到达每个格子的不同路径数目// 这里利用二维数组dp来记录到达各个格子的路径总数// 而obstacleGrid相当于地图,仅用于判断是否出现障碍物for(int i = 1, j = 1; i < m;){if(i >= m || j >= n) break;// 格子没障碍物才进行累计,有障碍物的格子其路径总数默认为0if(obstacleGrid[i][j] == 0)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];if(n == ++j){j = 1;i++;}}return dp[m - 1][n - 1];}
}

相关内容

热门资讯

安卓系统有小白条,便捷操作与个... 你有没有发现,在使用安卓手机的时候,屏幕下方总有一根小白条?这根小白条看似不起眼,却隐藏着不少秘密呢...
酷开还是安卓系统,深度解析两者... 亲爱的读者们,你是否在挑选智能电视时,对酷开系统和安卓系统感到纠结呢?别急,今天我就来给你详细剖析一...
电脑u盘装安卓系统,轻松实现移... 你有没有想过,把安卓系统装进电脑U盘里,是不是就能随时随地享受移动设备的便捷呢?想象不用再带着沉重的...
装了凤凰安卓系统进不去,无法进... 最近有个小伙伴遇到了一个棘手的问题,他的凤凰安卓系统手机突然装不进去了!这可真是让人头疼啊。下面,就...
安卓4.0导航系统,革新体验与... 你有没有想过,当你的手机升级到安卓4.0系统后,导航体验会有多么的翻天覆地?想象你正坐在车里,手握着...
怎样的才是安卓系统手机,怎样的... 你有没有想过,为什么安卓系统手机这么受欢迎呢?它们到底有什么特别的地方,让人爱不释手?今天,就让我带...
安卓什么系统最流畅省电,探寻最... 你有没有想过,为什么你的安卓手机有时候像蜗牛一样慢吞吞的,有时候又像火箭一样快?这背后其实和手机系统...
安卓系统限制如何解除,轻松解锁... 你是不是也和我一样,对安卓系统的限制感到头疼呢?有时候,那些小小的限制就像是无形的枷锁,束缚了我们的...
安卓系统网络电视盒子,智能娱乐... 你有没有发现,家里的电视越来越智能了?这不,最近我入手了一个安卓系统网络电视盒子,简直让我爱不释手。...
安卓穿越怎么更新系统,轻松实现... 亲爱的安卓用户们,你是否也和我一样,对手机系统更新充满了期待和好奇呢?每次系统更新,都仿佛给我们的手...
sony原生安卓系统吗,探索索... 你有没有想过,为什么有些手机用起来就是那么流畅,那么顺心?今天,我们就来聊聊这个话题:索尼手机的原生...
怎么给设备下安卓系统,设备安装... 你有没有想过,给家里的旧手机或者平板电脑装个全新的安卓系统,让它重获新生呢?这听起来是不是有点像给老...
安卓系统微信安装,畅享社交新体... 你有没有发现,最近你的手机里多了一个新伙伴——安卓系统微信安装?没错,就是那个我们每天离不开的社交神...
华为的安卓系统有哪些,打造智能... 你知道吗?华为的安卓系统最近可是火得一塌糊涂!作为一个紧跟科技潮流的数码爱好者,我可是对它充满了好奇...
安卓系统查询我的iphone,... 你有没有想过,你的安卓手机竟然能查询到你的iPhone信息?听起来是不是有点神奇?没错,这就是科技的...
致胜车载安卓系统刷机,畅享智能... 你有没有想过,你的车载安卓系统是不是已经有点儿“老态龙钟”了呢?别急,今天就来给你支个招——致胜车载...
安卓系统视频电话软件,便捷沟通... 你有没有想过,在这个信息爆炸的时代,即使身处千里之外,也能和亲朋好友实时畅聊呢?没错,就是那种可以边...
iphone14刷安卓系统,探... 你有没有想过,你的iPhone 14竟然也能装上安卓系统?是的,你没听错,就是那个以流畅著称的安卓系...
能够运行安卓的系统,兼容系统与... 你有没有想过,手机的世界里,竟然还有这样一群“异类”?它们不仅能够运行安卓系统,还能在性能和功能上与...
安卓免费私有云盘系统,探索安卓... 你有没有想过,你的手机里那些珍贵的照片、文件和视频,如果有一天突然丢失了,那该有多心疼啊!别担心,今...