一、什么是區(qū)間DP?

顧名思義：區(qū)間DP就是在區(qū)間上進行動態(tài)規(guī)劃，求解一段區(qū)間上的最優(yōu)解。主要是通過合并小區(qū)間的最優(yōu)解進而得出整個大區(qū)間上最優(yōu)解的DP算法。

二、核心思路

既然讓我求解在一個區(qū)間上的最優(yōu)解，那么我把這個區(qū)間分割成一個個小區(qū)間，求解每個小區(qū)間的最優(yōu)解，再合并小區(qū)間得到大區(qū)間即可。所以在代碼實現(xiàn)上，可以枚舉區(qū)間長度len為每次分割成的小區(qū)間長度（由短到長不斷合并），內(nèi)層枚舉該長度下可以的起點，自然終點也就明了了。然后在這個起點終點之間枚舉分割點，求解這段小區(qū)間在某個分割點下的最優(yōu)解。板子如下：

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++){//枚舉分割點，更新小區(qū)間最優(yōu)解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

三、樸素區(qū)間DP（n3)

例題：石子歸并1

（1）N堆石子擺成一條線?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的代價。計算將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)

括號里面為總代價可以看出，第一種方法的代價最低，現(xiàn)在給出n堆石子的數(shù)量，計算最小合并代價。

Input

第1行輸入一個數(shù)N（2 <= N <= 100) 第2 - N+1行每行輸入一個數(shù)，分別表示N堆石子的數(shù)量（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]);//更新狀態(tài)
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

四、題目變形（線性變環(huán)狀）

例題：石子歸并2

（1）題意：原題與上面相同，但是石子排列由線性排列變成環(huán)狀排列，求解。

（2）思路：環(huán)狀以后合并區(qū)間的情況就可以從后往前合并，最后合并完成可能是1~n,2~n~1,3~n~2.....這種n個石子合并的情況。所以我們可以破環(huán)成鏈，將前n-1各元素也放到n后面構成一個線性的環(huán)狀序列，在對這個序列dp即可

（3）代碼：codevs 2102 環(huán)狀石子歸并（求最大值和最小值）

#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;
}