算法动态规划

计数DP

字数统计: 1.6k字   |   阅读时长: 5分
, ,

摘要: 本文简要介绍一下计数类的问题，以及 leetcode 上的相关题目。

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

计数是组合数学的重要内容。不考虑用母函数等手段求解析解的话，计数问题一般有两大类解决方案。

  • 第一类是动态规划类解决方案，具体又有两种做法：
  1. 结果可以用带有组合数的公式表示，可以先推出带组合数的公式，然后用 DP 的方式求所需要的组合数, 参考 组合数。
  2. 可以找到用递推关系表示的结果，那么可以以 DP 的方式求这个递推关系，如果是线性递推关系，还可以用矩阵快速幂加速。参考 矩阵快速幂。
  • 第二种是组合数学类的解决方案，数学味比较浓，主要涉及以下几个知识点：
  1. 母函数
  2. 容斥原理
  3. 置换群和Polya计数
  4. 特殊计数序列：斯特林数，贝尔数等

本文涉及的问题都是第一种，这类计数问题可以用动态规划(找规律+列出递推方程)解决，称为计数 DP。

动态规划解决计数问题的方法论

前面我们提到计数 DP 有两种做法，组合数公式和递推式，用哪个方法需要看具体问题，组合数公式好找就用组合数公式，递推式好找就用递推式。

有的问题组合数公式和递推式都比较容易找到，那么两种做法都可以，以卡特兰数为例，它的组合数公式和递推式都比较好找，如下

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

从动态规划的角度看，计数类的动态规划问题，有以下两个特点：

  • 状态的各个决策之间满足加法原理，每个决策划分的几个子状态之间满足乘法原理。
  • 设计状态转移方程的决策方式和划分方法时，一个状态的所有决策之间都必须具有互斥性

下面我们整理一下 leetcode 上的相关题目。

常见的经典问题

路径问题

本题是计数 DP 的最简单的问题，当前状态等于各个决策对应的转以后的状态的求和，状态转移方程的主体是 $\sum$。

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

当障碍点很多的时候，如果以障碍点划分阶段，则本题代表了计数 DP 问题常见解决思路，即前面提到的：

  1. 设计状态转移方程的决策方式和划分方法时，一个状态的所有决策之间都必须具有互斥性。
  2. 状态的各个决策之间满足加法原理，每个决策划分的几个子状态之间满足乘法原理。

参考文章 不同路径系列问题。

卡特兰数

问题是求 $[1, n]$ 这 $n$ 个节点组成的二叉搜索树有多少种。

状态定义 $dp[i]$ 表示 $[1, i]$ 之间不同的二叉搜索树，则目标 $dp[n]$，边界 $dp[0] = 0$。

在状态 $dp[i]$ 时，所有的二叉搜索树按照根节点划分为 $j=1,2,\cdots,n$ 共 n 种，分别对应 $n$ 种决策。对于决策 $j$，即以 $j$ 为根节点，左子树有 $dp[j - 1]$ 种方案，右子树有 $dp[i - j]$ 种方案。由初等计数方法，状态转移方程如下：

以上转移方程也反映了以下前面提到的计数 DP 的特点：

  1. 设计状态转移方程的决策方式和划分方法时，一个状态的所有决策之间都必须具有互斥性。
  2. 状态的各个决策之间满足加法原理，每个决策划分的几个子状态之间满足乘法原理。

本题涉及到大组合数模质数的问题，涉及到卢卡斯定理，参考文章 组合数、卢卡斯定理。

铺砖问题

参考文章 多米诺与托米诺骨牌平铺。

涂色问题

参考文章：【DP难题】力扣1411-给Nx3网格图涂色的方案数

错排问题

斐波那契

以下的第一题是原始的斐波那契数列问题，列出状态转移方程后发现是线性的递推式，因此可以用矩阵快速幂。参考文章 矩阵快速幂及其动态规划优化中的应用。下面清单的其它的题目类似。

一些疑难杂症

发现隐晦的递推关系

需要在纸上画一画，猜想一些递推关系，然后再验证。有时也可以以自动机的形式给出递推关系。

参考文章 力扣940-不同的子序列，自动机DP。

发现子问题

以初等计数原理原理来划分阶段和子问题。

发现循环节

可以通过模拟找到循环节，然后在循环节的基础上进行推导。

Share