【亡羊补牢】挑战数据结构与算法 第68期 LeetCode 62. 不同路径(DP)
发布日期:2021-06-29 14:34:46
浏览次数:2
分类:技术文章
本文共 1148 字,大约阅读时间需要 3 分钟。
仰望星空的人,不应该被嘲笑
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?
示例 1:
输入: m = 3, n = 2输出: 3解释:从左上角开始,总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3输出: 28
提示:
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
机器人只能向右或向下移动一步,那么当前路径数等于左边路径数+上边路径数之和,不过初始化第0行和第0列路径数都为1。
/** * @param {number} m * @param {number} n * @return {number} */var uniquePaths = function (m, n) { let dp = new Array(m); // 初始化 第0行和第0列路径数都为1 for (let i = 0; i < m; i++) { dp[i] = new Array(n); dp[i][0] = 1; } for (let i = 0; i < n; i++) { dp[0][i] = 1; } // 当前路径数等于左边路径数+上边路径数之和 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1];};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108940460 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月15日 21时29分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
电气毕业生在国家电网都干啥工作?
2021-07-02
为什么LED灯会越用越暗?
2021-07-02
知乎热议:嵌入式开发中C++好用吗?
2021-07-02
这100道Linux常见面试题,看看你会多少?
2021-07-02
嵌入式开发中常用的几种通信接口总结
2021-07-02
为什么你学C++这么难?
2021-07-02
无人机破巡检难题,秒变电网卫士
2019-04-29
五年,我成为了一名嵌入式工程师。
2019-04-29
2020年电赛题目,命题专家们怎么看?
2019-04-29
PCB元器件摆放不可忽略的10个技巧
2019-04-29
掌握AI核心技术没有秘籍,能自己创造就是王道
2019-04-29
大学老师的月薪多少?实话实说:4万多一点……
2019-04-29
2020年电赛题目,命题专家权威解析!
2019-04-29
写论文,这个神器不能少!
2019-04-29
现在做硬件工程师还有前途吗?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
芯片为什么持续缺货?
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29
华为重磅反击,鸿蒙来了!
2019-04-29