动态规划

入门DP

• 如果某一问题有很多重叠子问题，使用动态规划是最有效的。

• 动态规划中，每一个状态一定是有上一个状态推导出来的，这一点区分于贪心。

背包DP

01背包

每个物品只有一个

1. 状态表示

1. 状态计算（迂回思想）

1. 遍历顺序

模板代码

 

📌

从代码中，可以发现，我们只需要维护当前这一行和上一行的状态，因此可以利用 将代码优化为一维。同时要注意数据污染问题

代码如下：

完全背包

每件物品有无穷多个

1. 状态表示

1. 状态计算

1. 遍历顺序

📌

这里同样可以使用滚动数组来进行一维优化，但这里不用要求背包容量j一定要从大到小遍历，因为我们可以从下图看出，完全背包虽然会使用到前面容量较小的背包，造成同一件物品添加多次，但这正是完全背包允许的呀

多重背包

第i中物品最多有si件

1. 状态表示

1. 状态计算——增加一层循环，对物品数量进行选择，进而转换为01背包问题

📌

由于三重循环，会导致时间复杂度过高，当数据量过大时，会造成超时，因此接下来使用 来去掉第三重循环

❓

另外可以通过 来进行优化

分组背包

物品在不同的组中，且每一组至多选择一件物品

1. 状态表示

1. 状态计算

线性DP

最长公共子序列

1. 状态表示：f[i][j]表示以i位结尾的字符串和以j为结尾的字符串的最长公共子序列长度

2. 状态计算
1. f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
2. f[i][j] = max(f[i - 1][j], f[i][j - 1]);

❗

提高：输出最长公共子序列

 

最短编辑距离

1. 状态表示

1. 状态计算

1. 手动推演

❗

还可以利用滚动数组进行优化，在此不做代码演示

❗

题目变式：编辑距离

 

区间DP

【模板题】石子合并

1. 状态表示

1. 状态计算

 

1. 初始状态

环形石子合并

这道题目和模板题的区别就在于一个是线性，一个是成环的，这时候我们很自然可以想到，在每个两点之间切断，变成线性之后使用模板代码即可：

📌

时间复杂度过高，会超时

📌

环形转化为链形：复制一遍数组，转化为长度为2N的链形数组 初始化会有所不同

能量向量

注意此题与环形石子合并的区别：

• 环形石子合并的代价都在石子本身

• 此题的代价都在项链石子的两侧，所以主体变为了两侧的能量值，不用进行初始化，个数也由n变为了n + 1，同时l,r两个也对应发生了改变

• 同时注意：这里的能量计算，必须涉及左、右、中三者之积，所以l < k < r，k不能取边界值

树形DP

没有上司的舞会

1. 题目示意图

1. 状态表示

1. 状态计算

1. 代码编写

1. 代码推演

状压DP

概念

核心：用二进制表示状态，用十进制数存储状态

判断约束条件时，要用到 ，学习状压DP，要先学会简单的位运算

解题思路：

1. 列举每行所有的状态（有2^n个状态），找出符合题意的合法状态，然后写出行内合法的位运算表达式

2. 找出行间兼容的位运算表达式

3. 列出状态表示

4. 状态计算

代码编写：

1. 先对每一行的合法状态进行预处理

2. 多重循环进行状态计算

小国王

1. 行内合法

1. 行间兼容

1. 状态表示

1. 状态计算

玉米田

1. 行内合法

1. 行间兼容

1. 状态表示

1. 状态计算

炮兵部队

1. 行内合法

1. 行间兼容

1. 状态表示

1. 状态计算

数位DP

概念

数位DP特点：求某个区间[L, R]内，满足某种性质的数的个数

解题技巧：

• 类似前缀和的思想，将区间[L, R]问题转换为[0, R] - [0, L - 1]求解

• 从高位到低位填数，要分类讨论

数字游戏

本题无题目链接，题目如下：（代码在输入方面有些许变化）

 

 

1. 状态表示

1. 状态计算

Windy数

1. 状态表示

1. 状态计算

 

 

记忆化搜索

数字三角形

❗

拓展

1. 记录最大和的路径

1. 左右走的次数有限制

经观察得：

• n为偶数时，最后一层落在的点一定在n/2或n/2+1

• n为奇数时，最后一层落在的点一定在n/2+1

❗

这个时候只能从上往下遍历了