【代码随想录训练营】【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];}
}

相关内容

热门资讯

安卓系统车机互联软件 你有没有发现,现在开车的时候,手机和车机之间的互动越来越频繁了呢?想象你正驾驶着爱车,一边享受着音乐...
荣耀play4安卓系统,智能生... 你有没有发现,最近手机圈里又掀起了一股热潮?没错,就是荣耀Play4这款新机!它不仅外观时尚,性能强...
安卓模拟苹果多开系统,打造跨平... 你有没有想过,在安卓手机上也能享受到苹果系统的多开功能呢?没错,这就是今天我要跟你分享的神奇话题——...
广汽埃安是安卓系统吗,搭载安卓... 你有没有想过,你的爱车广汽埃安,它的操作系统是不是安卓呢?这个问题,估计不少车友都在心里默默琢磨过。...
安卓系统是google的吗,谷... 你有没有想过,安卓系统是不是谷歌的亲生孩子呢?这个问题,就像是在问苹果是不是苹果树的宝宝一样,让人好...
安卓系统的设置程序下载,轻松掌... 你有没有发现,手机里的安卓系统设置程序真是五花八门,让人眼花缭乱?今天,就让我带你一起探索这个神秘的...
安卓系统的手机家园,打造个性化... 你有没有发现,现在手机的世界里,安卓系统的手机家园可是越来越热闹了呢!想象每天打开手机,就像走进了一...
安卓系统哪些相机可以调,支持实... 你有没有发现,手机拍照已经成为我们生活中不可或缺的一部分呢?无论是记录生活的点滴,还是捕捉美丽的瞬间...
安卓手机系统英文变中文,And... 你有没有发现,你的安卓手机上那些英文字母的系统提示,突然间变成了熟悉的中文呢?是不是觉得瞬间亲切感倍...
系统语言可以删除吗安卓,基于系... 你有没有想过,手机里的那些系统语言,是不是有时候觉得有点多余呢?比如,你是个地道的英语使用者,却总是...
安卓系统收取专利吗,揭秘科技巨... 你有没有想过,那个陪伴你每天刷手机、玩游戏、办公的安卓系统,它背后是不是也有自己的“小金库”呢?没错...
安卓屏幕怎么更新系统,轻松掌握... 亲爱的安卓手机用户们,你是不是也和我一样,时不时地想给手机来个“大变身”,让它焕然一新呢?没错,说的...
安卓系统有没有类似carpla... 你有没有想过,在安卓系统上,能不能也像苹果用户那样,轻松连接汽车音响系统呢?没错,我说的就是那个神奇...
安卓系统哪里升级包,生成与更新... 亲爱的安卓用户们,你是不是也和我一样,时不时地想给手机来个“大变身”,让它焕然一新呢?那就得提到那个...
安卓手机怎么恢复老系统,轻松恢... 手机用久了,是不是觉得系统越来越卡,功能也越来越不跟得上潮流了呢?别急,今天就来教你怎么把安卓手机恢...
安卓系统如何安装windows... 亲爱的安卓用户们,你是否曾幻想过在手机上体验Windows 7的韵味?别再羡慕那些拥有Windows...
旧的安卓系统怎么备份,轻松保存... 亲爱的安卓用户们,你是否曾经因为系统升级或者手机意外重启而担心丢失了珍贵的照片、联系人或者应用数据呢...
安卓手机系统文件被破坏,全面解... 手机突然间罢工了,是不是很崩溃?别急,今天就来聊聊安卓手机系统文件被破坏的那些事儿。相信我,掌握了这...
街头霸王四安卓系统,畅享格斗盛... 你知道吗?最近在安卓系统上,有一款游戏可是火得一塌糊涂,那就是《街头霸王四》!这款经典格斗游戏在安卓...
阿里tv安卓系统刷机,畅享智能... 你有没有发现,家里的阿里TV用久了,系统有点卡卡的呢?别急,今天就来教你怎么给它来个焕然一新的刷机大...