[Leetcode 62] 不同路径

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
一个机器人位于一个m x n网格的左上角,在下图中标记为 “Start” 。
notion image
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “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)
 
上一篇
[Leetcode 46] 全排列
下一篇
[Leetcode 79] 单词搜索