数据结构与算法 - 动态规划（计数问题）

发表于 2020-10-05 更新于 2021-02-09 分类于数据结构与算法

转载说明

计数是组合数学的重要内容。不考虑用母函数等手段求解析解的话，计数问题一般有两种做法：

以卡特兰数为例，

组合数公式：\(C_{n} = \dbinom{2n}{n} - \dbinom{2n}{n - 1} = \frac{1}{n + 1}\dbinom{2n}{n} = \prod_{k=2}^{n}\frac{n + k}{k}\)
递推式: \(C_{n} = \sum_{i=0}^{N-1}C_{i}C_{n-i-1}\)

在实际问题中，绝大多数都是用方法 2 来做，首先是因为递推关系相对好找一些，另外即使找到了组合数公式，依然要面临求组合数的问题。

在找递推关系时，有时需要手算若干例子找规律，然后猜想递推关系再验证。

下一小节我们用两道例题看一下这两种方法的思考过程。

==62. 不同路径 ==

本题更好想的做法是用动态规划来做，对于位置 (i,j)，它可能从上面或左面转移而来，因此状态设计和状态转移可以写成如下形式：

dp[i][j] := 从 (0,0) 到 (i,j) 的方法数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

按照计数问题的思路，我们可以这样想：从 (0,0) 走到 (m, n) 一共需要走 m + n - 2 步，其中 m - 1 步是向下走的，n - 1 步是向右走的。因此问题转化为从 m + n - 2 中选 m - 1 个，共有多少选法。

这个问题的组合数公式比较好写，如下：

\[\dbinom{m + n - 2}{m - 1}\]

我们可以用递推的方式求这个组合数，参考杨辉三角。

==276. 栅栏涂色 ==

很多问题用动态规划的思考方式思考时，可能会发现状态不是很好设计，或者不是很好转移，组合数公式也不好想，此时需要手算一些例子，看看能不能找到一些规律，找到突破口进而得到递推公式。

本题是典型的一例。

本题是问：k 种颜色，n 个栅栏，最多连续 2 个颜色相同，问有多少涂色的方案。

Step 1：手算若干例子，记 dp[i]:=i 个栅栏的方案数：

// n > 0, k > 0
n == 1: dp[n] = k
n == 2: dp[n] = k * k
n == 3: dp[n] = k * k * k - k
n == 4: dp[n] = k * (k * k * k - k) - k * k

Step 2：通过上述手算例子，可以猜想如下递推公式：

f[i] = k*f[i - 1] - f[i - 2]

如果要证明，可以考虑数学归纳法。

Step 3：将递推关系视为动态规划的状态转移，求解问题。

如果递推关系是线性的，可以用矩阵快速幂加速，这是下一章的内容。下一小节中有 16 道计数问题的练习题，练习这些题目时重点体会寻找递推关系的过程。