计数DP

  |  

摘要: 本文简要介绍一下计数类的问题,以及 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 上的相关题目,主要是 1800 以内的题目,1800 以上的题目还没有刷过,以后要是见到了再补充。

常见的经典问题

路径问题

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

卡特兰数

1259 要用卢卡斯定理求大组合数

铺砖问题

涂色问题

错排问题

斐波那契


一些疑难杂症

发现隐晦的递推关系

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

发现子问题

以组合计数的乘法原理来划分阶段和子问题。

发现循环节

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


Share