每日一题：LeetCode-62. 不同路径
刷题使我快乐，满脸开心.jpg
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
复制代码
示例 2：
复制代码
示例 3：
复制代码
示例 4：
复制代码
提示：
1 <= m, n <= 100题目数据保证答案小于等于
2 * 109
思路
典型动态规划题了，这里简单说下：
dp 定义
dp[i][j]含义为从[i，j]坐标去往终点的路径数量
状态转移方程
路径数量为从下方过来的路径数 加上 从右边过来的路径数之和
dp[i][j]=dp[i+1][j]+dp[i][j+1]
初始数据
只能从右方和下方过来，所以最右边一列只能从下放过来、最下方一排只能从右边过来，所以路径数都是1。
代码也基本就出来了。老样子，细节在代码注释
代码
复制代码
欢迎关注公众号交流更多题目~
版权声明: 本文为 InfoQ 作者【半亩房顶】的原创文章。
原文链接:【http://xie.infoq.cn/article/d29a51217898bc95f30429760】。文章转载请联系作者。
人生那么长，能写多少bug？ 2018-11-16 加入
我希望，自己永远是自己。我希望，远离bug。
评论