Preface
此方法由闫学灿推出，链接：闫氏DP分析法，从此再也不怕DP问题！_哔哩哔哩_bilibili 观看学习。
为 dp 问题提供了可供按照惯例的方式去解决，采用集合划分的思想，
但是需要大量的练习和总结，才能去快速解决此类问题，此类问题也有很多变形，
包括：背包问题、线性DP、区间DP、计数类DP、数位统计DP、状态压缩DP、树形DP等。
主要思路：
- 问题一般是求有限集合中的最优集合；
- 因此化零为整，抽象出状态表示，包括集合和属性，这一步需要大量的练习；
- 随后化整为零，寻找集合之间的最后一个不同点，求出状态转移方程；
- 不同类型的 dp 问题都可以以此来求解，但是细节有所不同；
也是听了这节视频以及整个 AcWing 平台题目的紧凑性，尤其是对 LCS 的讲解，
使得我豁然开朗，也让我决定在此平台不断学习算法。
Solution
01背包
问题详细描述：2. 01背包问题 - AcWing题库
按照上述思路进行分析：
代码如下（未优化）：
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
32
33
34
| import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int N = in.nextInt();
int V = in.nextInt();
int[][] objects = new int[N][2];
for (int i = 0; i < N; i++) {
objects[i][0] = in.nextInt();
objects[i][1] = in.nextInt();
}
System.out.println((new Main()).solution(N, V, objects));
}
}
private int solution(int N, int V, int[][] objects) {
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
int v = objects[i - 1][0];
int w = objects[i - 1][1];
if (j - v < 0) {
dp[i][j] = dp[i - 1][j];
continue;
}
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v] + w);
}
}
return dp[N][V];
}
}
|
完全背包
问题详细描述：3. 完全背包问题 - AcWing题库
按照上述思路进行分析：
代码如下（未优化）：
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
32
33
34
35
| import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int N = in.nextInt();
int V = in.nextInt();
int[][] objects = new int[N][2];
for (int i = 0; i < N; i++) {
objects[i][0] = in.nextInt();
objects[i][1] = in.nextInt();
}
System.out.println((new Main()).solution(N, V, objects));
}
}
private int solution(int N, int V, int[][] objects) {
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= V; j++) {
int v = objects[i - 1][0];
int w = objects[i - 1][1];
dp[i][j] = dp[i - 1][j];
int k = 1;
while (j - k * v >= 0) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v] + w * k);
k++;
}
}
}
return dp[N][V];
}
}
|
石子合并
问题详细描述：282. 石子合并 - AcWing题库
该题是区间DP，依然按照上述思路进行分析：
代码如下：
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
32
33
34
| import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int N = in.nextInt();
int[] objects = new int[N];
for (int i = 0; i < N; i++) {
objects[i] = in.nextInt();
}
System.out.println((new Main()).solution(N, objects));
}
}
private int solution(int N, int[] objects) {
int[] sum = new int[N + 1];
for (int i = 0; i < objects.length; i++) {
sum[i + 1] = sum[i] + objects[i];
}
int[][] dp = new int[N + 1][N + 1];
for (int len = 2; len <= N; len++) {
for (int i = 1; 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] + sum[j] - sum[i - 1]);
}
}
}
return dp[1][N];
}
}
|
最长公共子序列
问题详细描述：897. 最长公共子序列 - AcWing题库
按照上述思路进行分析：
代码如下：
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
| import java.util.*;
import java.math.*;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
String s1 = in.next();
String s2 = in.next();
System.out.println(new Main().getLcs(s1, s2));
}
}
public int getLcs(String s1, String s2) {
int n = s1.length();
int m = s2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[n][m];
}
}
|