# 动态规划
- 背包问题
- 线性DP
- 区间DP
- 计数类DP
- 数位统计DP
- 状态压缩DP
- 树形DP
- 记忆化搜索
# DP问题分析
状态表示
- 集合：每个状态表示一个集合
- 属性：集合会落实到某个属性上，这个属性可能是最大值、最小值、数量等。
状态计算/集合划分：将集合划分，这些集合在已经在之前的计算中已经计算过了。
划分原则：不重合(非必要)、不漏(必要)。
# 背包问题
# 01背包
状态表示
- 集合：定义状态(i, j)表示在前i个物品中选择物品体积之和小于等于j的所有选法的集合。
- 属性：f(i,j)表示在这个集合(也就是所有选法)中物品价值之和的最大值。
状态计算：划分为两个集合
- 不选第i件物品时：则状态就可以表示成在前i-1个物品中选择物品体积之和小于等于j的所有选法的集合,即f(i,j)=f(i−1,j)。
- 选择第i件物品时：物品i必选，先不考虑物品i，状态就可以变成在前i-1个物品中选择物品体积之和小于等于j-v[i]的所有选法的集合，即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])
朴素版：
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] v = new int[n+1];
int[] w = new int[n+1];
for(int i = 1; i <= n; i++){
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
// 从1开始，初始dp[0][j]=0，方便dp[i-1][j]不存在问题
int[][] dp = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
}
}
System.out.println(dp[n][m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
优化版：
需要注意两点
- 为了保证选择物品i的时候使用的是i-1的状态，需要倒序v更新dp。
- 可以省去
dp[i][j]=dp[i-1][j]，同时循环条件范围可以在[v[i], V]中，但是在朴素法中则不能这么做，因为要考虑取dp[i-1][j]的情况。
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] v = new int[n+1];
int[] w = new int[n+1];
for(int i = 1; i <= n; i++){
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int[] dp = new int[m+1];
for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
}
}
System.out.println(dp[m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 完全背包
状态表示和01背包一样
状态计算，可以划分为k+1个集合，k是能够选择i物品的最大数量
选择k件物品i时，所产生的最大收益为，k属于[0，V/v[i]]
f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])
可以化简
f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])
f(i,j−v[i])=MAX(f(i−1,j−v[i]),...,f(i−1,j−k∗v[i])+(k−1)∗w[i])
忽略f(i,j)中的第一项，我们可以将f(i,j)后面的项和f(i,j−v[i])一一对应，每一项f(i, j)要比它多一个w[i]，因此，状态转移可以化简为：
f(i,j)=MAX(f(i−1,j),f(i,j−v[i])+w[i])
对比01背包的方程：
f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i])
两者非常相似。可写出代码，由于f(i,j)第二项依赖于当前i，因此写优化版代码时无需倒序v。
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] v = new int[n+1];
int[] w = new int[n+1];
for(int i = 1; i <= n; i++){
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int[] dp = new int[m+1];
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <= m; j++){
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
}
}
System.out.println(dp[m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 多重完全背包
状态表示和状态计算和完全背包类似，只是选取物品的件数有限制
状态计算：k属于[0, s[i]]
f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])
我们可以使用朴素版直接写出代码，但是有些题参数较大，需要进行优化。
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] v = new int[n+1];
int[] w = new int[n+1];
int[] s = new int[n+1];
for(int i = 1; i <= n; i++){
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
s[i] = scanner.nextInt();
}
int[] dp = new int[m+1];
for(int i = 1; i <= n; i++)
// 因为依赖于i-1，需要倒着计算
for(int j = m; j >= 0; j--)
for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
dp[j] = Math.max(dp[j], dp[j-k * v[i]] + k * w[i]);
System.out.println(dp[m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
尝试化简
f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])
f(i,j−v[i])=MAX(f(i−1,j−v[i]),...,f(i−1,j−k∗v[i])+(k−1)∗w[i]+f(i−1,(k+1)∗v[i])+k∗w[i])
对比完全背包的优化，这里多了最后一项，因此无法像完全背包一样优化。
我们考虑这样一个问题
对于数字15，我们可以用1,2,4,8这4个数的组合表示0-15的任何一个数
对于数字17，可以用1,2,4,8,2这5个数的组合来表示0-17的中任何一个数
按照上面的问题，我们可以将物品i打包，打包后成为一个新物品，而这些打包的物品的组合可以拼凑出所有的s[i],对于每件打包的新物品只可以选1件或者不选，这样问题就转化成01背包问题了。
对于s[i]件物品，可以拆分成log2s[i]件物品，因此拆分所有的物品，最后的物品数量为O(N∗log2S)，算法的时间复杂度为O(N∗V∗log2S)
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int N = 12500; // 打包后物品数量可能为1000*log2000 约等于12000
int[] v = new int[N];
int[] w = new int[N];
int cnt = 1;
for(int i = 1; i <= n; i++){
int vt = scanner.nextInt();
int wt = scanner.nextInt();
int st = scanner.nextInt();
int k = 1;
// 将每件物品打包拆分
while(k <= st){
v[cnt] = k * vt;
w[cnt] = k * wt;
cnt++;
st -= k;
k *= 2;
}
if(st != 0){
v[cnt] = st * vt;
w[cnt] = st * wt;
cnt++;
}
}
// 01背包
int[] dp = new int[m+1];
for(int i = 1; i <= cnt; i++)
for(int j = m; j >= v[i]; j--)
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
System.out.println(dp[m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 分组背包
状态表示
- 集合：状态(i,j)表示前i组内选择体积不超过j的选择的集合。
- 属性：f(i,j)表示集合中某选择的价值最大值。
状态计算/集合划分，跟0,1背包类似
- 不选i组的物品，f(i,j)=f(i−1,j)
- 选择i组的第k件物品，f(i,j)=f(i−1,j−v[i][k])+w[i][k]
最后转移方程，k属于[1, s[i]],s[i]是i组的物品数量
f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i][k])+w[i][k])
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] v = new int[n+1][];
int[][] w = new int[n+1][];
int[] s = new int[n+1];
for(int i = 1; i <= n; i++){
s[i] = scanner.nextInt();
v[i] = new int[s[i]+1];
w[i] = new int[s[i]+1];
for(int j = 1; j <= s[i]; j++){
v[i][j] = scanner.nextInt();
w[i][j] = scanner.nextInt();
}
}
int[] dp = new int[m+1];
for(int i = 1; i <= n; i++)
for(int j = m; j > 0; j--)
for(int k = 0; k <= s[i]; k++)
// 注意if不能写在for循环里边
if(v[i][k] <= j)
dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);
System.out.println(dp[m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
背包问题总结
- 如果状态计算依赖与i-1，要倒序枚举V才能保证使用到的dp[j-v[i]]没有被更新过，表示是上一层的状态。
- 如果使用状态方程涉及到i-1，多定义一行，如果涉及j-1，多定义一列，从1开始枚举行可以较好的处理边界问题。
# 线性DP
线性DP指在状态计算的时候是线性更新的，这类DP的状态一般依赖于左边(i-1)或者上边(j-1)的状态，因此这类DP一般比较容易想。
# 最长上升子序列
状态表示
- 集合：(i)表示所有以a[i]结尾的上升子序列的集合
- 属性：f(i)表示所有集合大小的最大值
状态计算/集合划分，可以使用当前最长上升序列中上一个元素是a[0-j]的其中一个来划分。得状态转移：
f(i)=Math.max(1,{f(j)+1∣j∈[0,i−1],a[j]<a[i]})
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
int[] dp = new int[n];
int res = 0;
for(int i = 0; i < n; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(a[j] < a[i])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
res = Math.max(res, dp[i]);
}
System.out.println(res);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 二分+贪心优化
长度为i的上升子序列有很多，我们只用贪心地保存其上升子序列中最小末尾的数。
使用dp[i]表示长度为i的上升子序列中序列最后一个最小数。
dp[i]是单调递增的，在将一个数a[i]放置在上升子序列中时，只需要查找a[i]在dp[i]的插入位置就好。
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
int[] dp = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
// 哨兵
dp[0] = Integer.MIN_VALUE;
int res = 0;
for(int i = 0; i < n; i++){
int left = 0;
int right = res;
while(left <= right){
int mid = left + (right - left) / 2;
if(dp[mid] < a[i]){
left = mid + 1;
}else{
right = mid - 1;
}
}
res = Math.max(res, left);
dp[left] = a[i];
}
System.out.println(res);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 最长公共子序列
状态表示
- 集合：(i, j)表示a的前i个字符和b的前j个字符的所有公共子序列构成的集合。
- 属性：f(i,j)表示所有子序列的最长公共子序列。
状态计算/集合划分
不含a[i]，不含b[j]，f(i,j)=f(i−1,j−1)
包含a[i]，不含b[j]，f(i,j)=f(i,j−1)
不含a[i]，包含b[j]，f(i,j)=f(i−1,j)
包含a[i]，包含b[j]，f(i,j)=f(i−1,j−1)+1
注意在集合划分中包含a[i], 不含b[j]中，这个被划分出来的集合应该是的前i个字符和b的前j-1个字符的所有公共子序列构成的集合，且a[i]一定在公共子序列中，但是f(i, j-1)表示a[i]可能在也可能不在，也就是说这两个集合不相等，但是f(i, j-1)是包含前一个集合的，求max的话集合重叠也不影响最值。
同理f(i-1, j)也是一样的。
f(i-1, j-1)是包含在f(i, j-1)中的，所以可以去掉这个转移。
最后分析可得状态转移
f(i,j)=max(f(i−1,j),f(i,j−1),f(i−1,j−1)+1)
import java.util.Arrays;
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
String a = scanner.next();
String b = scanner.next();
int[][] dp = new int[a.length()+1][b.length()+1];
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp[0].length; j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
if(a.charAt(i-1) == b.charAt(j-1))
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
}
}
System.out.println(dp[a.length()][b.length()]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 最短编辑距离
状态表示
- 集合：
(i, j)表示A的前i个字符经过编辑得到B的前j个字符的操作的集合 - 属性：f(i,j)表示所有操作的最少操作次数
状态计算/集合划分
以A的第i个字符所进行的操作进行划分
- 删除：删除掉A的第i个字符，f(i,j)=f(i−1,j)+1
- 增加：在A的i位置增加一个字符B[j]，f(i,j)=f(i,j−1)+1
- 替换：将A[i]字符替换成B[j]，f(i,j)=f(i−1,j−1)+(A[i]==B[j]?0:1)
取三个操作的最小值即为f(i,j)。
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String A = scanner.next();
int m = scanner.nextInt();
String B = scanner.next();
int[][] dp = new int[n+1][m+1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if(i == 0 && j == 0)
continue;
if(i == 0){
dp[i][j] = j;
}else if(j == 0){
dp[i][j] = i;
}else {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1]
+ (A.charAt(i-1) == B.charAt(j-1) ? 0 : 1));
}
}
}
System.out.println(dp[n][m]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 区间DP
# 石子合并
状态表示
- 集合：(i,j)表示在区间
[i, j]合并石子的所有方案的集合。 - 属性：f(i,j)表示所有集合中某一种方案的最小体力值。
状态计算/集合划分
使用最后一次合并的分界点k来对集合进行划分，那么所花费体力为
f(i,k)+f(k+1,j)+sum(i,j)
即区间[i, k]合并成一堆的最小体力和区间[k+1, j]合并成一堆的最小体力加上这两堆合并在一起的体力值sum(i,j)，sum(i,j)为区间[i,j]之间的石子重量。
所以取这些所有分界点最小值就是f(i,j):
f(i,j)=min(f(i,k)+f(k+1,j)+sum(i,j)),k∈[i,j−1]
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
int[] preSum = new int[n+1];
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++){
nums[i] = scanner.nextInt();
}
for(int i = 1; i <= n; i++){
preSum[i] = preSum[i-1] + nums[i-1];
}
// 区间dp先枚举区间长度，再枚举起点
for(int len = 2; len <= n; len++){
for(int i = 0; i+len-1 < n; i++){
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
for(int k = i; k < j; k++){
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+preSum[j+1]-preSum[i]);
}
}
}
System.out.println(dp[0][n-1]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 计数类DP
# 整数划分
# 记忆化
DFS加记忆化，由于相同划分的不同顺序算作一个序列，因此要多加一个维度，保证数字选择是不递减的，以避免重复选择的情况。
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(new Main().helper(n,1, new Integer[n+1][n+1]));
}
// Memo[i][j]表示从数字i开始选择，总和为j的方案总数
public int helper(int n, int j, Integer[][] Memo){
int mod = (int)1e9+7;
if(Memo[n][j] != null)
return Memo[n][j];
if(n == 0)
return 1;
int count = 0;
for(int i = j; i <= n; i++){
count = (count + helper(n-i, i, Memo)) % mod;
}
return Memo[n][j] = count;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 动态规划
# 类比完全背包
可以将n看做是一个容量为n的背包，从1-n中选择几个数，使得恰好装满这个背包的方案数。
状态表示
集合：(i,j)表示从
1-i中选择几个数恰好容量为j的所有方案的集合属性：集合中元素(方案)的数量
状态计算/集合划分
- 选0个i
- 选1个i
- ...
- 选k个i
两个方程
f(i,j)=f(i−1,j)+f(i−1,j−i)+f(i−1,j−2∗i)+...+f(i−1,j−k∗i)
f(i,j−i)=f(i−1,j−i)+f(i−1,j−2∗i)+...+f(i−1,j−k∗i)
化简得
f(i,j)=f(i−1,j)+f(i,j−i)
代码：
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int mod = (int)1e9+7;
int[] dp = new int[n+1];
dp[0] = 1;
// 先枚举物品，在枚举容量
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
dp[j] = (dp[j] + dp[j-i]) % mod;
}
}
System.out.println(dp[n]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 另一种思路
状态表示
- 集合：(i,j)表示使用j个数能够凑成总和为i的方案的集合
- 属性：f(i,j)表示这些方案的数量
状态计算/集合划分
- 使用j个数能够凑成i，这j个数中最小值为1的集合，去掉一个1，则状态变为：f(i,j)=f(i−1,j−1)
- 使用j个数能够凑成i，这j个数中最小值不为1的集合，将这j个数都减去一个1，则状态变为：f(i,j)=f(i−j,j)，此时状态表示为j个数能够凑成
i-j的所有方案的数量。
将两个数量相加
f(i,j)=f(i−1,j−1)+f(i−j,j)
代码
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int mod = (int)1e9+7;
int[][] dp = new int[n+1][n+1];
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i][j] = (dp[i-1][j-1] + dp[i-j][j]) % mod;
}
}
// 最后还要统计所有得到n的方案数
int res = 0;
for(int i = 1; i <= n; i++)
res = (res + dp[n][i]) % mod;
System.out.println(res);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22