作者：whisper

链接：https://www.proprogrammar.com/article/1023

声明：请尊重原作者的劳动，如需转载请注明出处

动态规划中的计数型问题就是利用动态规划的算法思想去计算出解决这个问题有多少种方法。
比如，从起点走到终点，可以有多少条路径，注意，是多少条，而不是具体路线的描述。
当然也有具体每一条路线的问法，这是 dfs 的问题了。

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

1. 找到组合数公式，然后用 DP 的方式或者用含阶乘的公式求组合数
2. 找到递归关系，然后以 DP 的方式求这个递推关系，如果是线性递推关系，可以用矩阵快速幂加速

以卡特兰数为例，

在实际问题中，绝大多数都是用方法 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 个，共有多少选法。

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

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

计数问题递推关系法的思考过程

• 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：通过上述手算例子，可以猜想如下递推公式：

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

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

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

计数问题相关练习题

1. 路径问题
2. 卡特兰数
3. 铺砖问题
4. 斐波那契
5. 隐晦的递推关系

路径问题

组合数学中的格路模型，每个格路模型都有一个等价的放球模型

• 不同路径
• 不同路径 II

卡特兰数

• 不同的二叉搜索树 —— 卡特兰数
• 不相交的握手 —— 卢卡斯定理求大组合数

铺砖问题

• 多米诺和托米诺平铺

斐波那契

• 爬楼梯
• 使用最小花费爬楼梯
• 斐波那契数
• 第 N 个泰波那契数

隐晦的递推关系

• 骑士拨号器
• 屏幕可显示句子的数量 —— 可以通过模拟找循环节
• N 天后的牢房 —— 可以通过模拟找循环节
• 栅栏涂色
• 掷骰子的N种方法
• 学生出勤记录 II
• 不同的子序列 II —— 找规律

亲爱的读者：有时间可以点赞评论一下