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

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

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

---

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

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

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

---

62. 不同路径

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

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

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

提示：

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

动态规划

状态定义：
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)

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$ 的方案数，答案如下：

$$\binom{m + n - 2}{m - 1} = \frac{(m + n - 2)!}{(m - 1)!(n - 1)!}$$

代码 (Python)

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 来表示。

提示：

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

动态规划

状态定义：
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)

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$ 之前的所有障碍点，所以路线也不会遗漏。

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

$$dp[i] = \binom{x_{i} + y_{i}}{x_{i}} - \sum\limits_{j=0}\limits^{i-1}dp[j]\binom{x_{i} + y_{i} - x_{j} - y_{j}}{x_{i} - x_{j}}$$

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

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

$$\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1} \\ \binom{1}{1} = 1$$

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

代码 (Python)

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]

---