区间DP_区间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）.

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

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 ] 的组合。

代码如下：

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);