[数据结构与算法]动态规划（区间dp）

（一）、基础

1、特点：

（1）、合并：将两个或多个部分进行整合，能将问题分解为能两两合并的形式

（2）、求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值

（3）、复杂度：大多为$O(n^3)$，因此区间$dp$的数据范围一般在$100$左右

2、套路：第一层循环枚举区间长度，第二层循环枚举区间左端点，右端点也固定下来，第三层循环枚举区间的分割点

状态表示：$dp[i][j]$表示区间$[i,j]$能得到的最大（小）价值

状态转移：$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+cost)$

（二）、例题

1、石子合并

题意：在一个环上有$n$个石子$a_1,a_2......a_n$，进行$n?1$次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分，求最大得分和最小得分（$1\le n\le 100$）

题解：考虑不在环上的情况，那么我们可以把两堆石子合并看出成两个区间合并，代价即为两个区间内的石子数量的和

状态表示：$dp[i][j]$代表区间$[i,j]$石子堆能得到的最大（小）得分

状态转移方程：$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum(i,j))$

为了处理环，我们把n个石子堆变为$2?n$个石子堆，这样对$2?n$个石子堆进行区间$dp$，然后取从$i$往后$n$个石子堆能得到的最大值即可

int dp1[maxn][maxn], dp2[maxn][maxn];
int a[maxn], pre[maxn];
void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = n + 1; i <= 2 * n; i++)
	{
		a[i] = a[i - n];
	}
	n *= 2;
	for (int i = 1; i <= n; i++)
	{
		pre[i] = pre[i - 1] + a[i];
	}
	memset(dp1, 0x3f, sizeof(dp1));
	for (int i = 1; i <= n; i++)
	{
		dp1[i][i] = 0;
	}
	for (int sz = 1; sz < n; sz++)
	{
		for (int i = 1, j; (j = i + sz) <= n; i++)
		{
			for (int k = i; k < j; k++)
			{
				dp1[i][j] = min(dp1[i][j], dp1[i][k] + dp1[k + 1][j]);
				dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j]);
			}
			dp1[i][j] += pre[j] - pre[i - 1];
			dp2[i][j] += pre[j] - pre[i - 1];
		}
	}
	n /= 2;
	int ans1 = inf, ans2 = 0;
	for (int i = 1; i <= n; i++)
	{
		ans1 = min(ans1, dp1[i][i + n - 1]);
		ans2 = max(ans2, dp2[i][i + n - 1]);
	}
	cout << ans1 << '\n' << ans2 << '\n';
}

2、能量项链

题意：有一能量珠，串前一颗能量珠的头标记为$m$，尾标记为$r$，后一颗能量珠的头标记为$r$，尾标记为$r$，则聚合后释放的能量为$m?n?r$，新产生的珠子的头标记为$m$，尾标记为$n$，给定$n$个数， 第$i$个数为第$i$颗珠子的头标记（$1\le i\le m$）例如$23510$对应的石子就是$(2,3)(3,5)(5,10)(10,2)$，如果合并第一个和最后一个石子那么获得能量是$10?2?3$，求将所有珠子成一个能得到的最大能量（$4\le n\le 100$）

题解：类似于石子合并

状态表示：$dp[i][j]$代表区间$[i,j]$能获得的最大能量

状态转移：$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i?1]?a[k]?a[j])$

ll dp[maxn][maxn];
ll  a[maxn];
void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[n + i] = a[i];
	}
	a[0] = a[n];
	n *= 2;
	for (int sz = 2; sz <= n; sz++)
	{
		for (int i = 1, j; (j = i + sz - 1) <= n; i++)
		{
			for (int k = i; k < j; k++)
			{
				dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i-1] * a[k] * a[j]);
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n / 2; i++)
	{
		ans = max(ans, dp[i][i + n / 2 - 1]);
	}
	cout << ans << '\n';
}

3、括号匹配对数

题意：寻找括号匹配对数，不可重复使用

题解：

状态表示：$dp[i][j]$表示区间$[i,j]$内有多少对匹配的括号

状态转移：两种转移$dp[i][j]=dp[i+1][j?1]+match(i,j)$从稍小的区间转移，并且判断边界是否匹配

$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+match(k,k+1))$从分界点转移，并且判断分界点是否匹配

int dp[maxn][maxn];
char s[maxn];
int match(int a, int b)
{
	return s[a] == '(' && s[b] == ')' || s[a] == '[' && s[b] == ']';
}
void solve()
{
	while (cin >> s + 1)
	{
		if (s[1] == 'e' && s[2] == 'n' && s[3] == 'd' && s[4] == '\0')
			break;
		memset(dp, 0, sizeof(dp));
		int n = strlen(s + 1);
		for (int sz = 2; sz <= n; sz++)
		{
			for (int i = 1, j; (j = i + sz - 1) <= n; i++)
			{
				dp[i][j] = dp[i + 1][j - 1] + match(i, j);
				for (int k = i; k < j; k++)
				{
					dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + match(k, k + 1));
				}
			}
		}
		cout << dp[1][n] * 2 << '\n';
	}
}