算法动态规划

DP问题分类汇总-加强版

字数统计: 4.5k字   |   阅读时长: 16分
, , ,

摘要: 文章《dp问题分类汇总》的加强版

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

dp问题分类汇总 的加强版，《动态规划精讲》 系列的目录结构的主要参考。题目主要是 2000 以内的。

1、线性 DP

单串问题, 状态表示为 $dp[i]$，$i$ 为阶段

i 是单串 s 上的位置，作为阶段，具有时间或者位置等含义。没有附加维度。

最经典单串 LIS 系列问题：

参考文章：最长上升子序列LIS

最大子串和系列问题

参考文章：

打家劫舍系列问题: 不相邻子序列的最大和问题

参考文章：

其它

参考文章：

单串线性DP-一维状态表示阶段

双串问题, 状态为 $dp[i][j]$，$i,j$ 为阶段

i, j 分别是两个串上的位置。i, j 共同作为阶段，具有位置等含义。没有附加维度。

最经典双串 LCS 系列：

最长公共子序列LCS

字符串模糊匹配

双串线性DP,二维状态表示阶段

其它

双串线性DP,二维状态表示阶段

矩阵问题 dp[i][j] (i, j) 共同表示位置

dp[i][j]: i, j 分别是棋盘(矩阵)的横纵坐标。阶段划分有两种情况都比较常见：

  1. i 作为阶段，具有位置等含义。同时 j 是附加状态。
  2. i, j 共同作为阶段，具有位置等含义。没有附加维度。

棋盘DP

线性 DP，状态在阶段的基础上附加维度

高维线性DP,多维状态,阶段+附加维度

单串问题, 状态为 dp[i][k]

单串线性DP-多维状态,在阶段的基础上附加维度

i 是单串 s 上的位置，作为阶段，具有时间或者位置等含义。同时有附加一个维度 k，一般 k 会有长度，个数，次数，颜色等含义。

单串问题, 状态为 dp[i][k1][k2]

i 是单串 s 上的位置，作为阶段，具有时间或者位置等含义。同时有附加多个维度 k(k1, k2, …)，一般 k 会有长度，个数，次数，颜色等含义。

股票问题-自动机和动态规划

双串问题, 状态为 dp[i][j][k]

i, j 分别是两个串上的位置。i, j 共同作为阶段，具有位置等含义。同时有附加维度 k。一般 k 会有长度，个数，次数，颜色等含义。

矩阵问题, 状态为 dp[i][j][k]

i, j 分别是棋盘(矩阵)的横纵坐标。阶段划分有两种情况都比较常见：

  1. i 作为阶段，具有位置等含义。同时 j 是附加状态。
  2. i, j 共同作为阶段，具有位置等含义。没有附加维度。

同时有附加维度 k，一般 k 会有长度，个数，次数，颜色等含义。

多进程DP

步数 i 作为阶段，两个人的位置 (x1, y1, x2, y2) 作为状态。y1, y2 可以省略。

无显式串的线性 dp

2、区间 DP

区间长度为阶段，左端点为附加状态。可以用区间左右端点 (i, j) 来表示状态。

除此之外可能还有别的附加状态 k。

区间DP

减治型

分治型

3、背包 DP

已经处理的物品数为阶段，背包的总体积为附加状态。

01背包与完全背包
01背包和完全背包题目汇总

4、树形 DP

当前所在的深度为阶段，具体在该深度的哪个点为附加状态。可以用节点编号作状态表示。

除此之外可能有别的附加状态。

树形DP

5、状态压缩 DP

状态压缩DP

6、数位 DP

数位DP

满足某些条件的数字个数

求总的贡献

7、计数问题

计数问题-动态规划

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

  1. 找到组合数公式，然后用 DP 的方式求组合数
  2. 找到递归关系，然后以 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}$

路径问题(组合数学中的格路模型，每个格路模型都有一个等价的放球模型)：

卡特兰数：

铺砖问题：

涂色问题：

错排问题：

斐波那契：

隐晦的递推关系:

9、概率型 DP

求概率，求数学期望

10、博弈型 DP

博弈DP

前置知识：策梅洛定理，SG 定理，minimax

翻转游戏

Nim游戏

石子游戏

井字游戏

11、记忆化搜索

记忆化搜索

本质是 dfs + 记忆化，用在状态的转移方向不确定的情况，背后可能是任何一种类型的动态规划

12、DAG

拓扑序

HMM 前向传播

最长路径

自动机模型

13、其它

求决策序列(具体方案)

求最优决策序列数目(方案数)

同余类分解状态优化DP

倍增优化 DP

哈希表优化 DP

平衡树优化 DP

线段树优化 DP

预处理优化 DP

状态计算顺序优化

推公式优化 DP

单调队列优化 DP

DP方程组

二分优化DP

决策单调性

WQS 二分

Share