动态规划:区间d p小结

一,区间dp

顾名思义,区间dp即为在区间上求解最优值的问题。

其主要的思想就是先对于小区间进行求解,然后再利用小区间的最优解合并求得最大区间的最优解。

话不多说,直接上例题:

典例:(一道非常经典的区间dp的题目):石子合并

题意:有n堆石子排成一排,每堆石子有一定的数量。现在要将n对石子合并成为一堆。合并的过程中每次只能对相邻的两堆石子合并,每次合并要花费的代价为两堆狮子数量的和,经过n-1次合并后成为一堆,求解出总的代价的最小值。

举例:[4,1,1,4]->[4,2,4]->[4,6]->[10];

2 + 6 + 10 = 18

解题思路:

首先我们考虑最后一次合并,会发现前面一堆是由前k堆合并的,而后面一堆是由后面n-k堆合并在一起的。而代价是石子的总数量。

1,定义状态:设dp[i][j]表示把第 i 堆 ~ 第 j 堆合并的最小花费;sum[i][j]为第 i 堆 ~ 第 j 堆合并的石子数量。

2,转移方程:dp[i][j]=min(dp[i][j],dp[i][k]+dp[i][n-k]+sum[i][j]).

3,求解子状态:递归递推都可以,地推的话可以从区间短的枚举到区间长的。

4,复杂度O(n^3),状态O(n^2)。

代码(部分):

for(int len=2;len<=n;++len)
    for(int l=1;l+len-1<=n;++l)// len=r-l+1 -> r=l+len-1<=n
    {
        int r=l+len-1;
        for(int k=l;k<r;++k)
            dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[l][r]);
    }

区间dp模板:

1,定义状态:状态为DP(L,R)表示(L~R)的最优解

2,转移方程:枚举区间划分点DP(L,R)=DP(L,K)+DP(K+1,R)+cost(L,R,K)

3,递归或者递推求解:递推为从短区间枚举到长的。

二,例题环节

例题1:划分多边形

动态规划:区间d p小结

 解题思路:

(照搬模板)

dp[l][r]表示 l ~ r点构成的多边形剖分最小值。

cost(l ,r ,k)=w[l]*w[k]*w[r].

代码:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> v(n + 1, 0);
	for (int i = 1;i <= n;i++)
		cin >> v.at(i);
	vector<vector<int>> dp(n + 1,vector<int>(n + 1,0));
	for(int len=3;len<=n;len++)
		for (int l = 1;l + len - 1 <= n;l++)
		{
			int r = l + len - 1;
			if (len == 3)
				dp[l][r] = v[l] * v[r] * v[(l + r) / 2];
			for (int k = l+1 ;k+1 < r;k++)
				dp[l][r] =min(dp[l][k+1]+dp[k+1][r]+v[l]*v[r]*v[k+1], dp[l][k] + dp[k][r] + v[l] * v[r] * v[k]);
		}
	cout << dp[1][n];
	return 0;
}

例题2:最长回文子序列

求一个序列的最长回文子序列的长度

例如:[1,3,2,5,4,2,3,5,1]       答:7

解题思路:

dp[l][r]表示只考虑 l ~ r 范围的数字,构成的最长回文子序列长度

if(len==1) dp[l][r]=1;

dp[l][r]=max(dp[l][r-1],dp[l+1][r]);

if(a[l]==a[r]) dp[l][r]=max(dp[l][r],dp[l+1][r-1]+2);

代码:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> v(n + 1, 0);
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
	for (int i = 1;i <= n;i++)
		cin >> v.at(i);
	for(int len=1;len<=n;len++)
		for (int l = 1;len + l - 1 <= n;l++)
		{
			int r = len + l - 1;
			if (len == 1)
				dp[l][r] = 1;
			else
			{
				dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
				if (v.at(l) == v[r])
				dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
			}
		}
	cout << dp[1][n];
	return 0;
}

补充:

上述的石子合并里的石子序列是一个链状的序列;

若我们考虑到环状情况,合并的序列可能为:

第 i 堆,第 i+1 堆,第 i+2 堆,......,第 n 堆第 1 堆,.....第 i -1堆;

(环状从一处断开仍为链状。)

假设我们将原来的石子序列复制一遍,(1,2,3,.....,n,1,2,3,......,n),在新的长度为2n的序列上做区间dp,dp[i][i+n-1]的结果即为从i 断开的结果。

复杂度O(n^3)

综合训练:

[CQOI2007]涂色PAINT_牛客题霸_牛客网 (nowcoder.com)

感兴趣的可以练一练。

上一篇:CF1062A A Prank


下一篇:Can you answer these queries 1?