区间dp的总结_什么是区间dp

1、区间dp含义

区间dp 常用dp[i][j] 来表示，含义是在区间[i,j]之间最大的…或是否可以成功。这里提供以下三个题来熟悉区间dp。

2、经典区间dp问题，合并果子

 现在设有n堆的果子，每堆果子根据果子数量的不同需要耗费不同的体力，现在想把这些果子有次序的合并为一堆，消耗的体力等于两堆果子的重量之和。现在求耗费的最小的体力数多少。
比如 5 8 9 3
5+8=13 消费13体力 13 9 3
9+3=12 消费12体力 13 12
13+12=25 消费25体力
总体力消耗为 13+12+25=50
输入格式：
第一行一个正整数N（N<=300），表示沙子的堆数N。
第二行N个正整数，表示每堆石子的质量(<=1000)。
输出格式：
一个正整数，表示最少需要消耗多少体力。
 思路：对于这种最少，最多，是否成功的问题一般都可以采用动态规划。而这道题又是明显的区间dp问题。
 我们设dp[i][j] 表示合并区间 第i堆到第 j堆所需要的最少体力。 而且容易想到dp[i][j]=dp[i][k]+dp[k][j]。对于k，这里代表的是从想合并i->k这段区间的，和合并k->j 这段区间的。但是我们还需要将dp[i][k]和dp[k][j]这两堆合并，体力消耗为sum[j]-sum[i-1]。这里sum[j]代表的是从第0堆到第j堆所需要的体力。是一个前缀和。所以状态转移方程:
$$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+sum[j]-sum[i-1])$$
所以区间DP的一种写法就是：第1层循环枚举长度len，第2层循环枚举左端点l（这样就知道了右端点r），第3层循环枚举中间点k

	const int N = 310;
	int n;
	int s[N];//前缀和
	int dp[N][N];
	int main()
	{
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];
		for(int len=2;len<=n;len++)//（当len=1时说明只有一堆，直接返回）区间dp   先枚举区间长度，再                                     //枚举区间范围
			for (int i = 1; i + len - 1 <= n; i++)
			{
				int j = i + len - 1;
				dp[i][j] = 1e8;
				for (int k = i; k < j; k++)
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
			}
		cout << dp[1][n] << endl;//最终需要求出从1-n范围的
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、预测赢家(leetcode 486)

 思路：这道题也可以转换为区间dp进行求解。dp[i][j] 表示当数组剩下的部分为下标 i 到下标 j 时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。由于每次当前玩家只能去两端的值，所以不用像上面那道题那样还要枚举距离。
只有当 $i\le j$ 时，数组剩下的部分才有意义。
当 i<j 时，当前玩家可以选择 $\text{nums}[i]$或 $\text{nums}[j]$，然后轮到另一个玩家在数组剩下的部分选取数字。在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：

$$dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])$$
最后判断 $dp[0][nums.size()-1]$的值，如果大于或等于0，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。

第一种方法：

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
	vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
	for (int i = 0; i < nums.size(); i++)
		dp[i][i] = nums[i];
    //从下到上填表
	for (int j = 1; j < nums.size(); j++)
	{
		for(int i=0;i<j;i++)
		{
			dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
		}
	}
	return dp[0][nums.size()-1]>=0;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二种方法：我们其实可以发现合并果子那道题是解决区间dp的经典解法，可以将方法套过来直接使用。唯一注意的是在区间i ->i+len-1是，合并果子还需要枚举这个区间的任意一点，而这道题只需要枚举两端，所以可以不需要第三层for循环。

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
	vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
	for (int i = 0; i < nums.size(); i++)
		dp[i][i] = nums[i];
    //从下到上填表
	for (int len = 2; len <= nums.size(); len++)
	{
		for (int i = 0; i+len-1 <nums.size(); i++)
		{
            int j=i+len-1;
			dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
		}
	}
	return dp[0][nums.size()-1]>=0;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4、最长回文子串(leetcode 5)

 思路：和leetcode486一样，$dp[i][j]$表示从s[i]到s[j]是否为回文串,分为两种情况：
1、 s[i]!=s[j] dp[i][j]=false;
2、s[i]==s[j]时，需要根据dp[i+1][j-1]进行判断 分两种情况
(1) 当j-1-(i-1)<1, 也就是j-i<3时，说明dp[i+1][j-1]是一个字符，dp[i][j]=true;
(2) 或者j-i>3时, dp[i][j]=dp[i+1][j-1];
这时,如果dp[i][j]=true且 j-i+1>maxlen, 记录当前 begin=i,maxlen=j-i+1

这个题的代码基本和上面的代码类似，但要注意的是

class Solution {
public:
    string longestPalindrome(string s) {
        /*
        dp[i][j]表示从s[i]到s[j]是否为回文串
        when s[i]!=s[j]   dp[i][j]=false;
        when s[i]==s[j]时，需要根据dp[i+1][j-1]进行判断  分两种情况 
       (1) 当j-1-(i-1)<1, 也就是j-i<3时，说明dp[i+1][j-1]是一个字符，dp[i][j]=true; 
       (2) 或者j-i>3时, dp[i][j]=dp[i+1][j-1];
       这时,如果dp[i][j]=true且 j-i+1>maxlen, 记录当前 begin=i,maxlen=j-i+1
        */
        int n=s.size();
        if(n<=1) return s;
        bool dp[n][n];
        for(int i=0;i<n;i++)
        {
           dp[i][i]=true;
        }
        string ret;
        for(int j=0;j<n;j++)
        {
            for(int i=0;i<=j;i++)
            {
                if(s[i]!=s[j]) dp[i][j]=false;
                else
                {
                    if(j-i<3) dp[i][j]=true; 
                    else
                    {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j])
                {
                    if(j-i+1>ret.size())
                    {
                        ret=s.substr(i,j-i+1);
                    }
                }
            }

        }
        if(ret=="") ret=s[0];
        return ret ;
    }
};
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

总结：

区间dp第一题的解法是通用解法，需要枚举区间的距离。而当不需要枚举距离时，2，3题的解法就可以通用，他们只需要填半张表即可。