Leetcode - 不同路径(DP)
发布日期:2021-07-01 00:15:03
浏览次数:2
分类:技术文章
本文共 697 字,大约阅读时间需要 2 分钟。
题目描述
一个机器人位于一个 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
解题思路
这是一道简单的dp题,找到转移方程就行了,我们可以用dp[i][j]来表示到达i,j处的不同路径,则
dp[i][j]=1.i=0,j=0;
dp[i][j]=dp[i-1][j]+dp[i][j-1].i>0,j>0;
我们也可以不用开一个二维数组,因为题上只需要我们提供最后的答案就行了,我们可以用一个一维的数组,
dp[0]=1,dp[j]=dp[j-1]+dp[j];
int uniquePaths(int m, int n) { int maxV[110] = {0}; maxV[0] = 1; for (int i = 0; i < m; i++) for (int j = 1; j < n; j++) maxV[j] = maxV[j - 1] + maxV[j]; return maxV[n - 1];}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84297628 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月15日 21时26分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
正则表达式简介(微软)--7.普通字符
2019-05-01
正则表达式简介(微软)--8.特殊字符
2019-05-01
正则表达式简介(微软)--9.非打印字符
2019-05-01
正则表达式简介(微软)--10.字符匹配
2019-05-01
正则表达式简介(微软)--11.限定符
2019-05-01
正则表达式简介(微软)--12.定位符
2019-05-01
正则表达式简介(微软)--13.选择与编组
2019-05-01
sqlserver过滤字符串中的空格的自定义函数
2019-05-01
关于Alexa排名作弊的一些解惑
2019-05-01
把Alexa工具条改装成木马(1)
2019-05-01
把Alexa工具条改装成木马(2)
2019-05-01
把Alexa工具条改装成木马(3)
2019-05-01
把Alexa工具条改装成木马(5)
2019-05-01
女秘书PK老板,“邮件门”传遍全国外企圈
2019-05-01
开源项目-如何在贡献开源项目的过程中提升自己
2019-05-01
算法-二叉树-序列化和反序列化二叉搜索树
2019-05-01
算法-Hash-回文
2019-05-01
算法-Hash-单词规律
2019-05-01
算法-Hash/BitSet-字母异位词分组
2019-05-01
算法-水位-无重复字符的最长子序列
2019-05-01