type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
一个机器人位于一个
m x n网格的左上角,在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
例 1:
例 2:
解法一:动态规划
机器人每次只能向 右 或 下 走一步,
设
dp[i][j] 为从起点 (0,0) 到达 (i,j) 的路径总数。转移方程如下:
即当前格子的路径数 = 来自上方的路径 + 来自左方的路径。
边界条件:
- 第一行:只能从左边来 →
dp[0][j] = 1
- 第一列:只能从上边来 →
dp[i][0] = 1
最终答案为
dp[m-1][n-1]。 复杂度
- 时间:O(m·n)
- 空间:O(m·n)
优化1:空间压缩(滚动数组)
每次只需上一行与当前行,因此只保留两行。
- 时间:O(m·n)
- 空间:O(2n)
优化2:进一步压缩为一维
只用一维数组
cur[j] 保存当前行状态。利用右侧更新的顺序,使得 cur[j] 始终表示当前行的路径数。
- 时间:O(m·n)
- 空间:O(n)
解法二:组合数学(Combinatorics)
机器人总共要走
(m-1) 次向下 + (n-1) 次向右即一共走
m + n - 2 步,其中任意 (m-1) 步为“向下”。因此路径总数为:
或不使用
comb():复杂度
- 时间:O(min(m, n)) (计算组合数时较小阶的乘积)
- 空间:O(1)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-62-不同路径
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 46] 全排列
下一篇
[Leetcode 79] 单词搜索