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

相关内容

热门资讯

内幕交易炒股避损7万被罚60万... 2026年11月12日,中国证监会北京监管局发布了一份针对有研硅(688432.SH)普通员工刘冰的...
普京:难怪您会选这里作为APE... 为期两天的亚太经合组织工商领导人峰会在深圳举行。俄罗斯总统普京在18日的峰会上发表致辞。普京表示,深...
猪价重回9元关口 养殖仍面临亏... 11月17日早上,28个重点监测地区瘦肉型标猪出栏均价为9.12元/公斤,比前一天上涨了一毛钱。尽管...
温泉直播拍顾客还拉黑质疑者 隐... 近日,有网友发帖称,上海汤连得温泉的直播间镜头长期对准洗浴区通往三楼休息区的楼梯通道。这里是顾客上下...
湖北老虎墩墓地出土漆立人凤形勺... 11月18日上午,国家文物局召开“考古中国”重大项目重要进展工作会,发布四项考古最新进展。其中,湖北...
小米回应“雷军深圳发言紧张” ... 在深圳举办的2026年APEC工商领导人峰会上,雷军分享了他对AI现状的看法。他认为技术变化迅速,但...
为何都说“APEC需要中国” ... 2026年APEC工商领导人峰会在深圳举行,吸引了21个经济体的两千多位工商界代表。峰会首日议程紧凑...
黄金会跌回400元一克吗?专家... 黄金会跌回400元一克吗?专家预测不乐观!黄金价格在2024年大幅上涨后,许多人关心2025年的走势...
东风61列装释放战略信号引发岛... 东风-61洲际导弹近日正式列装火箭军,这一消息引发了台湾岛内媒体的广泛关注。据央视网《海峡两岸》节目...
也门首都萨那传出巨大爆炸声 多... 据总台报道员消息,当地时间17日,也门首都萨那传出巨大爆炸声。另据也门胡塞武装消息,沙特阿拉伯主导的...
潮汕牛肉丸圈粉无数中外媒体记者... 潮汕牛肉丸圈粉无数中外媒体记者。11月13日,在APEC会议周新闻中心,浓郁的岭南烟火气在镜头与键盘...
哈啰单车新车型被吐槽“单车刺客... 近日,有网友在北京一路口扫到一辆蓝色新款哈啰单车,页面显示骑行30分钟收费15元,价格远高于普通共享...
女子蹲金价1年不到3万拿下32... “低价加工黄金,只要30元!”近日,在浙江湖州长兴的乡间小路上,这声吆喝吸引了村民刘大妈的注意。远低...
女子腿被压车轮下旁边女子竟指挥... 11月16日(发布),一段网友发布的视频引发热议。视频中,一名女子腿部被压在车轮下,趴在地上痛苦不已...
油价或再下调 今日价格 新一轮... 油价或再下调 今日价格 新一轮调价窗口将启。11月首调油价大跌后,新一轮油价调整有望继续下降。调整窗...
医生建议最近穿袜子睡觉:入睡快... 最近降温,每天晚上钻进被窝就像钻进“冰窖”——躺了半天双脚还是凉的。很多人觉得忍忍就好了,或等睡着就...
陆毅女儿宣布出道,“爸爸去哪儿... 继黄磊女儿10月时尚活动完成“内娱首秀”、郭涛儿子11月入选电影频道2026“星辰大海”青年演员优选...
14岁男孩带内耗妈妈运动治好内... 近日,山东菏泽。一段孩子陪妈妈运动,并喊着:“内耗的妈妈养不出明媚的孩子”的视频火了。记者联系上视频...
新娘强忍泪水与兄弟姐妹吃“分家... 广东汕尾。按照当地习俗,婚礼上新娘与兄弟姐妹吃“分家饭”,新娘强忍泪水,弟弟崩溃大哭,妹妹不敢直视姐...
消防员被困电梯名场面 网友:主... 近日,成都消防开展工作室意外被困电梯于是求救,赶来救援的同行忍不住现场“无情嘲笑”。网友:主打一个自...