区间DP

107 阅读 0 评论 71 点赞

我是靠谱客的博主怡然黑裤，这篇文章主要介绍区间DP，现在分享给大家，希望可以做个参考。

一.区间dp

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。写法主要有记忆化搜索和递推的形式.

例题：

矩阵连乘最优

给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

一个 n×m 矩阵由 n 行 m 列共 n x m 个数排列而成。两个矩阵 A 和 B 可以相乘当且仅当 A 的列数等于 B 的行数。一个 n x m 的矩阵乘以一个 m × p 的矩阵等于一个 n × p 的矩阵，运算量为 n x m x p. 矩阵乘法满足交换律，显然不同的乘法的运算量是不同的。现在给出 n 个矩阵，并输入 n+1 个数，第 i 个矩阵是 a[i-1] * a[i] .
求出最少的运算量。

考虑最后一次做乘法的位置，这会将原问题分解成两个规模较小的子问题。
需要枚举最后一次乘法的位置，转移的复杂度为O（n）.
合法子问题区间为 [ i, j ] 其中 1≤ i ≤ j ≤n，故状态数为O（n^2）.
总时间复杂度为O（n^3）.

代码如下：（记忆化搜索的形式写法）

复制代码

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
package 线性DP;
import java.util.Scanner;
public class 矩阵连乘 {
static int max = (int) 1e9;
static int[] a = new int[200];
static int[][] dp = new int[200][200];
static int matrix(int l, int r) {
if (dp[l][r] != max)
return dp[l][r];
for (int i = l; i < r; i++) {
// 以i为中点分开[l,r] 那么就是左边的[l,i]先计算，右边[i+r,r]先计算,然后左右相乘计算
dp[l][r] = Math.min(dp[l][r], matrix(l, i) + matrix(i + 1, r) + a[l - 1] * a[i] * a[r]);
}
return dp[l][r];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 第 i 个矩阵是 a[i-1]*a[i];
for (int i = 0; i <= n; i++) {
a[i] = sc.nextInt();
}
// dp[i][j]表示（i,j）范围内矩阵乘法的最优计算量
for (int i = 0; i < 200; i++) {
for (int j = 0; j < 200; j++)
dp[i][j] = max;
}
for (int i = 0; i <= n; i++)
dp[i][i] = 0;
}
}

括号匹配

给出一串仅由 ( ) [ ] 四个字符组成的字符串，求其中一个最长的子序列，使得其括号匹配。
空串括号匹配。
若 s 括号匹配，则（s）与 [ s ] 括号匹配。
若 s，t 括号匹配，则 st 括号匹配。

比如：

( ( ( ) ) ) =6

( ) ( ) ( ) =6

( [ ] ] )=4

直接按照题面中的意思来进行状态转移即可。
对于区间 [ l,r ] ，如果Sl=Sr，，则其可以由 [ l+1，r-1 ] 转移得到。
否则枚举中间间断点m，认为该区间是 [ l,m ] 和 [ m+1,r ] 的组合。

代码如下：

复制代码

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
36
37
38
package 线性DP;
import java.util.Scanner;
public class 括号匹配 {
static char[] s;
static int[][] f = new int[200][200];
// 判断 第x个位置和第 y个位置是否相同
static int match(int x, int y) {
char x1 = s[x], y1 = s[y];
if (x1 == '(' && y1 == ')') {
return 1;
} else if (x1 == '[' && y1 == ']') {
return 1;
} else {
return 0;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
s = ("-" + sc.next()).toCharArray();
for (int i = 1; i < n; i++) {
f[i][i + 1] = match(i, i + 1);
}
// 枚举j-i的距离d
for (int d = 2; d < n; d++) {
for (int i = 1; i + d <= n; i++) {
int j = i + d;
f[i][j] = f[i + 1][j - 1] + match(i, j);// 判断第i位和第j位是否匹配，匹配则加一
for (int k = i; k < j; k++) {
f[i][j] = Math.max(f[i][j], f[i][k] + f[k + 1][j]);
}
}
}
System.out.println(f[1][n] << 1);
}
}

石子合并

有N堆石子排成一排(可以成环)，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子个数的和，经过N-1次合并后成为一堆。求出总的代价最小值。

如果不要求相邻两堆合并，可使用小根堆来做。

代码如下：

复制代码

package 线性DP;
import java.util.Scanner;
public class 合并石子 {
static int max = (int) 1e9;
static int[] a;
static int[][] dp1;
static int dpp(int l, int r) {
if (dp1[l][r] != 0)
return dp1[l][r];
if (l == r)
return 0;
int res = max;
for (int i = l; i < r; i++) {
res = Math.min(res, dpp(l, i) + dpp(i + 1, r) + a[r] - a[l - 1]);
}
return dp1[l][r] = res;
}
static void plus(int n) {
int[][] f = new int[200][200];
for (int d = 1; d < n; d++) {
for (int i = 1; i + d <= n; i++) {
int j = i + d;
f[i][j] = max;
for (int k = i; k < j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
}
}
}
System.out.println(f[1][n]);
}
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
a = new int[n * 2 + 1];
dp1 = new int[2 * n + 1][2 * n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
a[i + n] = a[i];
}
for (int i = 1; i <= 2 * n; i++) {
a[i] = a[i - 1] + a[i];
}
dpp(1, 2 * n);
int ans1 = max;
for (int i = 1; i <= n; i++) {
ans1 = Math.min(ans1, dp1[i][i + n - 1]);
}
System.out.println(ans1);

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
36
37
38
39
40
41
42
43
44
45
46
47
package 线性DP;
import java.util.Scanner;
public class 合并石子 {
static int max = (int) 1e9;
static int[] a;
static int[][] dp1;
static int dpp(int l, int r) {
if (dp1[l][r] != 0)
return dp1[l][r];
if (l == r)
return 0;
int res = max;
for (int i = l; i < r; i++) {
res = Math.min(res, dpp(l, i) + dpp(i + 1, r) + a[r] - a[l - 1]);
}
return dp1[l][r] = res;
}
static void plus(int n) {
int[][] f = new int[200][200];
for (int d = 1; d < n; d++) {
for (int i = 1; i + d <= n; i++) {
int j = i + d;
f[i][j] = max;
for (int k = i; k < j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
}
}
}
System.out.println(f[1][n]);
}
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
a = new int[n * 2 + 1];
dp1 = new int[2 * n + 1][2 * n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
a[i + n] = a[i];
}
for (int i = 1; i <= 2 * n; i++) {
a[i] = a[i - 1] + a[i];
}
dpp(1, 2 * n);
int ans1 = max;
for (int i = 1; i <= n; i++) {
ans1 = Math.min(ans1, dp1[i][i + n - 1]);
}
System.out.println(ans1);