不同路径系列问题:计数DP,以初等计数原理划分阶段和子问题

  |  

摘要: 状态的各决策间满足加法原理,决策划分的子状态间满足乘法原理

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


动态规划中的计数类问题,主要强调“不重不漏”。因此如果用动态规划解决的话,子结构的划分,以及阶段的推导需要比较仔细。通常状态的各个决策之间满足加法原理,每个决策划分的几个子状态之间满足乘法原理。

62. 不同路径63. 不同路径 II 是动态规划解决计数问题最经典的问题。

本文我们就解决不同路径系列问题,并且重点看一下当计数问题复杂的时候,如何按照初等计数的加法原理和乘法原理来做划分阶段和状态表示。


62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

提示:

1
2
1 <= m, n <= 100
题目数据保证答案小于等于 2e9

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

示例 3:
输入:m = 7, n = 3
输出:28

示例 4:
输入:m = 3, n = 3
输出:6

动态规划

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[i][j] := 从 (0, 0) 出发到 (i, j) 的方案数

初始化
dp[0][0] = 1

答案
dp[m - 1][n - 1]

状态转移
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if i > 0:
dp[i][j] += dp[i - 1][j]
if j > 0:
dp[i][j] += dp[i][j - 1]
return dp[m - 1][n - 1]

组合数学

对于 $m$ 行 $n$ 列的起盘,从左上走到右下,一共要 $m + n - 2$ 步,其中要走 $m - 1$ 步向下、$n - 1$ 步向右。

由于棋盘中没有任何障碍,$m - 1$ 步向下和 $n - 1$ 步向右就可以随意交换顺序。因此总方案数相当于从 $m + n - 2$ 中选出 $m - 1$ 的方案数,答案如下:

代码 (Python)

1
2
3
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return math.comb(m + n - 2, m - 1)

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

提示:

1
2
3
4
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义:
dp[i][j] := 从 (0, 0) 出发到 (i, j) 的方案数

初始化
dp[0][0] = 0 (obstacleGrid[0][0] = 1)
1 (obstacleGrid[0][0] = 0)

答案
dp[m - 1][n - 1]

状态转移
若 obstacleGrid[0][0] = 1,则 dp[i][j] = 0,否则:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
return 0
dp[0][0] = 1
for i in range(m):
for j in range(n):
if obstacleGrid[i][j] == 1:
continue
if i > 0:
dp[i][j] += dp[i - 1][j]
if j > 0:
dp[i][j] += dp[i][j - 1]
return dp[m - 1][n - 1]

动态规划:依乘法原理划分阶段

当棋盘很大,而障碍点有限的时候。我们可以考虑根据障碍点进行计数。如果我们能知道从左上到右下至少经过一个障碍点的路线数量,那么用 $\binom{m + n - 2}{m - 1}$ 减去该数量即得答案。

之前的动态规划算法中,每一步是一个阶段,在一个阶段可以选择向右走或向下走去到下一个阶段,一共 $m + n - 1$ 个阶段。

现在我们以障碍物作为阶段,在一个阶段可以选择走到某一个更靠近右下的障碍物,或者直接到终点去到下一个阶段,这样阶段数取决于路线上障碍物的数量。

把所有障碍点按照以横坐标 $x$、纵坐标 $y$ 为第一、第二关键字排序。并且将 $(0, 0)$ 视为第 0 个障碍点,$(m - 1, n - 1)$ 为第 $N + 1$ 个障碍点。排序后,第 $i$ 个障碍点的坐标为 $(x_{i}, y_{i}$。

记 $dp[i]$ 表示从左上角走到第 $i$ 个障碍点,且途中不经过其它障碍点的路径个数。

此时枚举从左上角到 $(x_{i}, y_{i})$ 经过的第一个黑色格子,记该格子为 $j$,也就是说从左上到 $(x_{j}, y_{j})$ 不能经过别的障碍点,其路经数为 $dp[j]$。从 $(x_{j}, y_{j})$ 到 $(x_{i}, y_{i})$ 随便走,其路线是组合数 $\binom{x_{i} + y_{i} - x_{j} - y_{j}}{x_{i} - x_{j}}$。

由于要求的是从左上到右下至少经过一个障碍点的方案数,所以我们就枚举第一个经过的障碍点 $j$,使得从左上到 $j$ 构成了一个整体,这段路不能经过障碍点。

  • 由于第一个经过的障碍点不同,不同的 $j$ 对应的路线肯定不会重复。
  • 由于 $j$ 取遍了 $i$ 之前的所有障碍点,所以路线也不会遗漏。

结合乘法和加法原理,就有了以下状态转移方程:

上式左半部分是从左上到 $(x_{i}, y_{i})$ 随便走的方案数,有半部分是从左上到 $(x_{i}, y_{i})$ 经过至少一个障碍点的方案数。

首先通过以下公式预处理出 $\binom{m + n - 2}{m - 1}$ 以下的所有组合数:

然后按照顺序枚举出所有障碍点,记录到一个数组中,然后再该数组上推导状态转移方程即可。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
return 0

# 预处理组合数
C = [[0 for _ in range(m)] for _ in range(n + m - 1)]
for i in range(n + m - 1):
C[i][0] = 1
for i in range(1, n + m - 1):
for j in range(1, min(i + 1, m)):
C[i][j] = C[i - 1][j] + C[i - 1][j - 1]

# 按顺序枚举出所有障碍点,边枚举边推导状态转移方程
dp = []
ps = []
for x in range(m):
for y in range(n):
if obstacleGrid[x][y] == 1 or (x == m - 1 and y == n - 1):
tmp = C[x + y][x]
for j in range(len(dp)):
if ps[j][0] > x or ps[j][1] > y:
continue
tmp -= dp[j] * C[x + y - ps[j][0] - ps[j][1]][x - ps[j][0]]
dp.append(tmp)
ps.append((x, y))

return dp[-1]

Share