LeetCode 62. 不同路径(DP)
发布日期:2021-07-01 03:13:44
浏览次数:3
分类:技术文章
本文共 805 字,大约阅读时间需要 2 分钟。
文章目录
1. 题目信息
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?说明:m 和 n 的值均不超过 100。示例 1:输入: m = 3, n = 2输出: 3解释:从左上角开始,总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右示例 2:输入: m = 7, n = 3输出: 28
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-paths 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。2. 解题
跟一样的题目
- 先将第一行,第一列的状态表填好
- 再填充剩余状态表
dp[i][j] = dp[i-1][j]+dp[i][j-1]
class Solution { public: int uniquePaths(int m, int n) { int dp[n][m], i, j; for(i = 0; i < n; ++i) dp[i][0] = 1; for(j = 1; j < m; ++j) dp[0][j] = 1; for(i = 1; i < n; ++i) for(j = 1; j < m; ++j) dp[i][j] = dp[i-1][j]+dp[i][j-1]; return dp[n-1][m-1]; }};
转载地址:https://michael.blog.csdn.net/article/details/100148537 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月18日 04时46分54秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
使用ViewPager加载页面出现空白
2019-05-01
ImageView scaleType
2019-05-01
RecyclerView notifyItem闪屏问题
2019-05-01
dubbo学习笔记 十一 dubbo-rpc之模块
2019-05-01
motan学习笔记 五 opentracing学习入门
2019-05-01
求列表最长子序列
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
网络编程之 Socket函数 (二)
2019-05-01
网络编程之 Socket的模式(一) --- “阻塞/非阻塞” 与 “同步/异步”
2019-05-01
ffmpeg & mplayer & vlc 手册
2019-05-01
Go语言并发组件
2019-05-01
简析STUN协议
2019-05-01
使用 Minidumps 和 Visual Studio .NET 进行崩溃后调试
2019-05-01
Debug 和 Release 编译方式的本质区别
2019-05-01
struts返回xml数据例子
2019-05-01
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01