算法动态规划

计数DP

字数统计: 1.1k字   |   阅读时长: 3分
, ,

摘要: 本文简要介绍一下计数类的问题，以及 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