区间DP实例讲解

69157 阅读 0 评论 0 点赞

一、什么是区间DP?

顾名思义：区间DP就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的DP算法。

二、核心思路

既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。板子如下：

for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

三、朴素区间DP（n³)

例题：石子归并1

（1）N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

例如： 1 2 3 4，有不少合并方法

1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)

1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)

1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。

Input

第1行输入一个数N（2 <= N <= 100) 第2 - N+1行每行输入一个数，分别表示N堆石子的数量（1 <= A[i] <= 10000)

Output

输出最小合并代价

Sample

（2）转移方程：

dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);

j~ends堆合并 = 较小的（原来，分割点i坐部分重量 + 分割点i右边部分重量 + 合并后两堆总重量）

注：可以用sum[j] - sum[i - 1]表示i~j堆的重量！

（3）代码：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int stone[105];
int dp[105][105];
int sum[105];
int main()
{
    int n;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    memset(dp,INF,sizeof(dp));
    for(int  i =1;i<=n;i++){
        scanf("%d",&stone[i]);
        sum[i] = sum[i - 1] + stone[i];//重量
        dp[i][i] = 0;
    }
    for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+sum[ends]-sum[j-1]);//更新状态
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

四、题目变形（线性变环状）

例题：石子归并2

（1）题意：原题与上面相同，但是石子排列由线性排列变成环状排列，求解。

（2）思路：环状以后合并区间的情况就可以从后往前合并，最后合并完成可能是1~n,2~n~1,3~n~2.....这种n个石子合并的情况。所以我们可以破环成链，将前n-1各元素也放到n后面构成一个线性的环状序列，在对这个序列dp即可

（3）代码：codevs 2102 环状石子归并（求最大值和最小值）

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f
int stone[105];
int dpmin[205][205];//最小
int dpmax[205][205];//最大
int sum[205];
int main()
{
    int n;
    scanf("%d",&n);
    memset(sum,0,sizeof(sum));
    memset(dpmin,INF,sizeof(dpmin));
    memset(dpmax,-1,sizeof(dpmax));
    for(int  i =1;i<=n;i++){
        scanf("%d",&stone[i]);
        sum[i] = sum[i - 1] + stone[i];
        dpmin[i][i] = 0;
        dpmax[i][i] = 0;
    }
    for(int i = 1;i<=n;i++){
        sum[i+n] = sum[i+n-1]+stone[i];//展开的n后面的n-1~1重量
        dpmin[i+n][i+n] = 0;
        dpmax[i+n][i+n] = 0;
    }
    for(int len = 1;len<=n;len++){//长度还是最大n
        for(int j = 1;j+len<=2*n;j++){//起点枚举最大到2*n-1,ends<=2*n-1
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//注意！i<ends！！！因为i=ends时，dp[ends+1][ends]是不成立的！
                dpmin[j][ends] = min(dpmin[j][ends],dpmin[j][i]+dpmin[i+1][ends]+sum[ends]-sum[j-1]);
                dpmax[j][ends] = max(dpmax[j][ends],dpmax[j][i]+dpmax[i+1][ends]+sum[ends]-sum[j-1]);
            }
        }
    }
    int ansmin = 0xfffffff;
    int ansmax = -1;
    for(int i = 1;i<=n;i++){
        ansmin = min(ansmin,dpmin[i][i+n-1]);//找1~n,2~n~1,3~n~2....的合并n个堆的中最大和最小的值
        ansmax = max(ansmax,dpmax[i][i+n-1]);
    }
    cout<<ansmin<<endl;
    cout<<ansmax<<endl;
    return 0;
}