目录

1. 动态规划综述
2. 常见题型总结——背包问题
3. 线性DP
4. 区间DP
5. 计数类DP
6. 数位统计DP
7. 状态压缩DP
8. 树形DP
9. 记忆化搜索

1. 动态规划综述

这里不是很想长篇大论、用一堆记不住的专业名词去像教材那么讲动态规划，所以就调了个人认为的一些重点来介绍

动态规划问题是一种以空间换时间的做法，这是很显然的，我们在dp的时候，会额外开一个数组（若采用记忆化搜索，占据的额外空间是系统自带的栈区域。额外使用的空间用来存储之前的一些数据，之前算出来的数据会被下一阶段接着使用计算。我们并没有对重复的情况进行额外的计算，而是选择保存下来。

从这一点也可以看出来它为什么比$dfs$快，爆搜往往就是硬算，即使是剪枝优化，也不妨碍它可能把特别常用的数据算了$n$次。同样，对暴搜进行一些优化就成了记忆化搜索，记忆化搜索是dp的一种形式。$dp$是一种思想，而不是囿于固定的格式(当然写题时候还是需要记住一些格式来提高效率)

思路

不过$dfs$没有能直接硬套的模板，但是也是有迹可循的。可以按照状态表示和状态计算两个角度考虑

状态表示里面，一般用一个多维数组来表示一个集合。而这个值是集合的某一种属性$(max$, $min$, $cnt)$

状态计算首先要想的是如何划分，对应的也就是集合划分，最后一步怎么由上一步转换过来的，然后写出计算表达式

考虑好边界条件与优化条件后就可以直接写程序了

2. 背包问题

2.1 01背包

状态表示：

$f[i][j]$表示只用前$i$个装容量为$j$的背包的价值，属性是最大值

状态划分：

当前状态可以分为，不选当前物品，$f[i][j]$ = $f[i - 1][j]$和选当前物品，$f[i][j] = f[i - 1][j - v[i]] + w[i]$

我们得到的状态转移方程
$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$

因为每次状态转移只用到上一层和本层的情况，所以可以用滚动数组优化。又因为是上一层转移过来的，所以是倒叙枚举

不带优化的代码

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ )
        f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

优化后的

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

2.2 完全背包

状态表示

$f[i][j]$表示只装前$i$个物品，背包体积为$j$能容纳的最大价值

状态计算

很明显，我们可以模仿01背包，考虑第$i$个物品不装，或者装一个，装两个......（如果装的下）

这样得到的状态转移方程为

f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - v[i]] + w[i], 
            f[i - 1][j - v[i] * 2] +w[i] * 2], .......)

这样的时间复杂度是很高的,$O(n m ^ 2)$

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ )
        for (int k = 0; k * v[i] <= j; k ++ )
            f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + w[i] * k);

我们可以看下$f[i][j - v[i]]$的状态划分情况

f[i][j - v[i] = max(f[i - 1][j - v[i]], f[i - 1][j - v[i] * 2] + w[i] * 1, 
                f[i - 1][j - v[i] * 3] + w[i] * 2..)

将它与$f[i][j]$相比，我们可以发现除去第$i$个物品一个不选的情况，剩下的每一项$f[i][j]$都比$f[i - 1][j - v[i]]$多一个$w[i]$
$f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]$

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ )
    {
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }

同样的，我们可以发现，这一次，每一次的状态只与上一个状态有关，所以依然可以用滚动数组优化。
如果本次物品不选，那么就不变。剩下的是由本层状态转移来的，所以需要正序枚举

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= m; j ++ ) // 正序写
        if (j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);

2.3 多重背包

我们需要对物品按二进制位进行打包，这样可以等效选择任意合法数量的某种物品。然后按01背包做就可以了。所以最后的状态表示和状态计算和01背包是一模一样的，核心代码如下

题头

const int N = 12010, M = 2010; // N是拆分后物体总数， M 是背包容量

int n, m;
int v[N], w[N];
int f[M]; // 滚动数组优化后的dp数组

拆分过程

    cin >> n >> m;

    int cnt = 0; // 记录打包后的物品个数，从1开始打包
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) //一直减2的倍数
        {
            cnt ++ ;
            v[cnt] = a * k; // 打包后的体积与价值
            w[cnt] = b * k;
            s -= k; // 剩下需要打包的量
            k *= 2; // 先 * 2，下次剩余的就是与下一个比较了
        }
        if (s > 0) // 如果剩下的C存在
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt; // 打包完成

01背包过程

    for (int i = 1; i <= n; i ++ ) // 01背包
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

2.4 分组背包

数据存储

$v[N][N]$和$w[N][N]$，第一维表示是第几组，第二维表示这一组里面的数据

状态表示

$f[i][j]$表示前前$i$组中选物品，背包空间为$j$时候的最大价值

状态计算

这里，我们枚举每一组的每一个物品

$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k])$

同样的，我们可以和之前一样运动滚动数组优化，因为是与上一个状态有关，所以倒叙列举

$i, j, k$顺序问题

$(1)$ $if$的判断条件不能放到$for$里面，因为$k$每一组物品的空间大小不是连续的
$(2)$ $i, j, k$不可以调换顺序，它们的顺序是由状态转移方程决定的，换了后意义就不存在了，纵使可以ac，但是那也是碰巧撞上的

for (int i = 1; i <= n; i ++ ) // dp
    for (int j = m; j >= 0; j -- )
        for (int k = 0; k < s[i]; k ++ )
            if (v[i][k] <= j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

3. 线性DP

3.1 数字三角形

这道题课上是自顶向下的做法，自下而上会少去很多步骤，答案就是$f[1][1]$

状态表示: $f[i][j]$

集合：所有从起点走到(i, j)点的路径
属性：经过数字和的最大值

状态计算

我们可以发现，任何一个点只会由左上方和右上方两个点（如果存在）转移下来

f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]

因为下标里面有-1，所以我们下标要从1开始

for(int i = n; i >= 1; i--)
    for(int j = 1; j <= i; j++)
        f[i][j] += max(f[i+1][j], f[i+1][j+1]);

3.2 最长上升子序列

状态表示

$f[i]$表示以下标为$i$的数字结尾的上升子序列的集合

属性：子序列长度的最大值

状态计算

基础做法

每次从前向后遍历，如果该点前面有点数值比它小，就试着更新一下

i表示当前点，j小于i也是下标
if (a[i] < a[j]) f[j] = max(f[j], f[i] + 1);

优化做法

我们开辟一个辅助数组，q[ ], q[i]表示长度为$i$的最长子序列的最后一个数字的最小值

我们每次将一个新的数字插入到子序列时，因为要尽可能的让子序列变长，所以我们要尽可能的向长的子序列后面插入，因为$q$[ ]是单调递增的，所以我们可以二分出来应该添加到哪里，找到数组中比当前数据小的最大值，然后添加到它的后面

添加后，这个最长子序列的长度就会加一，而之前与现在添加后长度相等的子序列最后一个数字比当前处理数据大，所以要修改q[i + 1]

    int len = 0; // 当前上升子序列长度最大值
    for (int i = 0; i < n; i ++ ) // 依次处理每一个数据
    {
        int l = 0, r = len; // 二分找到，小于当前数据的最大值
        while (l < r) // 二分过程
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid; // 二分条件
            else r = mid - 1;
        }
        len = max(len, r + 1); 
        // 每次更新完，如果是接到最后的，长度会增加，所以需要考虑上升子序列的最大值是否更新
        q[r + 1] = a[i]; // q[i + 1]也需要更新
    }

3.3 最短编辑距离

状态表示 f[i][j]

集合：f[i][j]表示的是a串前i个字母变成b串前j个字母的所有方式
属性：数量

状态计算

最后一步总是有三种操作，増删改。我们总是让问题出现的时候，就解决它，所以我们修改的一定是最后一个字母。之前修改的总是会包含在现在，因为我们最后统计方案数量时候，不看修改顺序，只看是怎么修改的

题干是可以删増改任意位置，不过我们在第一时间修改它，所以总会在它是最后一个字母时候就修改它

下面分类也是默认了这个前提

f[i][j] = f[i - 1][j] 删 + f[i][j - 1] 増 + f[i - 1][j - 1] + 1/0 改

a[i] == b[i]时候，就不需要改，反之需要改就加一次操作，最后一步的修改

初始化

第一个字符串前n个字母变成第二个字符串前0个字符时，每次都是删除操作，所以是n

同理，第一个字符串前0个字母变成第二个字符串前n个字符，每次都是添加操作，所以也是n

for (int i = 0; i <= m; i ++ ) f[0][i] = i;
for (int i = 0; i <= n; i ++ ) f[i][0] = i;

核心代码如下

    for (int i = 0; i <= m; i ++ ) f[0][i] = i; // 初始化
    for (int i = 0; i <= n; i ++ ) f[i][0] = i;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); // 増和删两种情况一定存在，直接算
            if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); 
            // 改这一个不一定存在所以分类讨论下
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }

4. 区间DP

例题：石子合并

状态表示 $f[i][j]$

集合：将第$i$堆石子到第$j$堆石子合并的全部方式
属性：$min$，合并的最小花费

状态计算

线性的区间DP，一般就是三层循环，第一层枚举区间长度，第二层枚举左端点

这是一个简单的区间$dp$。首先，每次到最后一步，肯定是两堆石子合并成一堆。所以我们每次枚举划分结点，将一段范围划分成两个更小的范围，因为我们是从小到大计算的所以更小的范围一定被求解过了（或者直接记忆化搜索做）

a[]是存储石子堆里石子个数的，f[][]是dp数组，k是i ~ j间的划分点
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[i] + a[i + 1] + ... + a[j])

核心代码如下

    for (int len = 2; len <= n; len ++ ) // 区间dp， 枚举区间长度
        for (int i = 1; i + len - 1 <= n; i ++ ) // 枚举左端点
        {
            int l = i, r = i + len - 1; // 求出右端点
            f[l][r] = 1e8; // 初始化一个比较大的数，防止一直为0
            for (int k = l; k < r; k ++ ) // 枚举分割点
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]); // 利用区间和
        }

5. 计数类DP

这道题，感觉很难从达到做一题窥一类的，贴一个对应习题题解吧
AcWing 900. 整数划分 https://www.acwing.com/solution/content/79258/

6. 数位统计DP

同样的，这道题更像是模拟，并没有一个套路或者典型的感觉
AcWing 338. 计数问题 https://www.acwing.com/solution/content/80780/

7. 状态压缩DP

状态压缩，顾名思义，把表示一堆数字的状态压缩到一个数字上，这个数字二进制表示的某一位的0和1表示对应的状态。这是一种表示状态的思路，如果不压缩，往往数组就得多出一个维度，空间可能就超了

附两道例题的题解
AcWing 291. 蒙德里安的梦想 https://www.acwing.com/solution/content/80783/
AcWing 91. 最短Hamilton路径 https://www.acwing.com/solution/content/80801/

8. 树形DP

同样的，这种东西也是一个思路，做一遍大概能懂有这么个类就够了。还是给出经典例题的题解

AcWing 285. 没有上司的舞会 https://www.acwing.com/solution/content/80842/

9. 记忆化搜索

记忆化搜索是对暴搜的一种优化，等价于动态规划。也就是说记忆化搜索是动态规划思想的一种实现方式，是通过搜索来实现的

优点

$(1)$ 记忆化搜索可以避免搜到无用状态，特别是在有状态压缩时
$(2)$ 不需要注意转移顺序（这里的“转移顺序”指正常 dp 中 for 循环的嵌套顺序以及循环变量是递增还是递减）
$(3)$ 边界情况非常好处理，且能有效防止数组访问越界
$(4)$ 有些 dp（如区间 dp) 用记忆化搜索写很简单但正常 dp 很难
$(5)$ 记忆化搜索天生携带搜索天赋，可以使用技能“剪枝”！

缺点

$(1)$ 致命伤：不能滚动数组
$(2)$ 有些优化比较难加
$(3)$ 由于递归，有时效率较低但不至于 TLE（状压 dp 除外）

附例题
AcWing 901. 滑雪 https://www.acwing.com/solution/content/80846/