题目说明
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
图片来源leetcode
示例1:
- 输入：m = 3, n = 7
- 输出：28
示例2:
- 输入：m = 3, n = 2
- 输出：3
- 解释：
- 从左上角开始，总共有 3 条路径可以到达右下角。
- 1. 向右 -> 向下 -> 向下
- 2. 向下 -> 向下 -> 向右
- 3. 向下 -> 向右 -> 向下
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 109
解题思路
利用动态规划算法
定义状态f[i][j]为到达(i,j)位置的路径条数
f[0][0] = 1,那么最终m*n的表格，到达右下角的路径条数即为f[m-1][n-1]中的值
每次移动情况，如果当前位置：
向下：f[i][j] = f[i-1][j]
向右: f[i][j] = f[i][j-1]
向下，向右:f[i][j] = f[i-1][j]+f[i][j-1]
如果你还不理解的话，观看一下流转图：
以2*2的网格为例
说明，从f[0][0]出发，那么开始时，节点f[0][0]=1，
节点f[0][1]只能由于f[0][0]向右移动得到,即 f[0][1]=f[0][0]
节点f[1][0]同理，只能f[0][0]下移得到。即 f[1][0]=f[0][0]
节点f[1][1]，可以由于f[0][1]向下移动，f[1][0]向右移动。两种移动方式得到。即：f[1][1] = f[0][1] + f[1][0]
最后，f[m-1][n-1]，右下角的位置即为最终结果
如果你还不理解的话，建议你手动画一下2*3的表格移动状态的转移过程。
代码实现
- 1func uniquePaths(m int, n int) int {
- 2 f := make([][]int,m)
- 3 for i:= range f{
- 4 f[i] = make([]int,n)
- 5 }
- 6 f[0][0] = 1
- 7 for i:=0;i
- 8 for j:=0;j
- 9 if i>0 && j>0 { //可以向下，向右移动
- 10 f[i][j] = f[i-1][j] + f[i][j-1]
- 11 }else if i>0 { //可以向下移动
- 12 f[i][j] = f[i-1][j]
- 13 }else if j>0 { //可以向右移动
- 14 f[i][j] = f[i][j-1]
- 15 }
- 16 }
- 17 }
- 18 //循环结束后，走到了终点
- 19 return f[m-1][n-1]
- 20}
复杂度分析
- 时间复杂度：O(m*n)
- 空间复杂度: O(m*n)
