區間dp總結

最經典的一個區間dp問題是矩陣鍊乘問題，算導和一些算法書上都有介紹，

給出N個矩陣和他們的規格，滿足相鄰的矩陣都能合法的進行矩陣乘法的運算，我們定義一個(a*b)和一個(b*c)的矩陣做乘法，乘法次數為b*b*a*c

求解最少的能将所有矩陣乘在一起的次數。

第一次見這個問題是cj同學随手拍給我的一道題，當時就感覺像以前寫過的一道區間dp，然後紙上推了半天最後成功過了樣例！

我們把要求解的這個問題看做是f(1,N),最後的一次操作肯定會剩下兩個矩陣然後乘一起，我們不妨枚舉一下這個分割點，

會發現 f(i,j)=MIN{f[i][k]+f[k+1][j]+r[i]*w[k]*r[k+1]*w[j]},方程的意義就是将矩陣從第k個分開，隻要我們知道前k個和後(N-k)個矩陣相乘的最優次數，此時得最優次數也能得出。我們還發現這個轉移方程的依賴關系不是像一些線性的隻有知道前面才能推導後面，而是由長度較小的區間慢慢的推導出長度較大的區間，最後得出答案，這也是區間dp的奧妙所在。

 與之類似的問題有經典的石子合并問題:  ​​http://acm.nyist.net/JudgeOnline/problem.php?pid=737​​

這個和上面的就是同一種做法，dp[i][j]=MIN{dp[i][k]+dp[k+1][j]+sum(i,j)}

1  
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define inf 0x3f3f3f3f
 5 int a[205],dp[205][205];
 6 int sum[205][205];
 7 int SUM(int s,int e)
 8 {
 9     if(sum[s][e]!=-1) return sum[s][e];
10     int sumn=0,i;
11     for(i=s;i<=e;++i) sumn+=a[i];
12     return sum[s][e]=sumn;
13 }
14 int main()
15 {
16     int n,m,i,j,k;
17     while(cin>>n){memset(dp,inf,sizeof(dp));memset(sum,-1,sizeof(sum));
18         for(i=1;i<=n;++i) scanf("%d",&a[i]),dp[i][i]=0;
19         for(k=2;k<=n;++k)
20             for(i=1;i+k-1<=n;++i){
21     int minn=inf;
22     for(j=i;j<=i+k-1;++j)  if(dp[i][j]+dp[j+1][i+k-1]<minn) minn=dp[i][j]+dp[j+1][i+k-1];//j表示分割點
23     dp[i][i+k-1]=minn+SUM(i,i+k-1);
24             }
25         cout<<dp[1][n]<<endl;
26     }
27     return 0;
28 }
29 
30 
31      

有些問題會在此類問題的基礎上做一些變化，可能會限制區間大小或是限制區間的起始點，處理起來可能沒那麼容易。

​​http://www.lydsy.com/JudgeOnline/problem.php?id=1996​​

上面就是一道區間dp的問題，是不是沒那麼推導方程了，題目說的看起來好像也很複雜。

我們還是從區間來看待問題，大問題的解就是[1,N]之間初始隊形的方案數，如何由小區間推導呢，如果單純的用dp[i][j]表示[i,j]之間的方案數得話，由于我們不知道

最後一個元素前面是哪個元素推導起來似乎沒那麼容易。比如目标序列是(1,2,4,3),在知道(1,2,4)的初始方案中，隻有末尾是1和2的才能順利推出目标序列，

通過觀察我們發現最後一個元素的位置隻會出現在頭部或者尾部，不妨多加一維表示他的位置,這樣方程就可以寫出來了,

dp[i][j][0]=MIN{ dp[i][j-1][1] | a[j]>a[j-1]  ,   dp[i][j-1][0]  | a[j]>a[i]}

dp[i][j][1]=MIN{ dp[i+1][j][1] | a[i]<a[j]    ,   dp[i+1][j][0] | a[i]<a[i+1]}

注意隻有一個元素的區間 dp[i][i][0]和dp[i][i][1]隻要有一個是1就好了，不然會重複。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define mod 19650827
 5 int dp[1005][1005][2];
 6 int a[1005];
 7 int f(int l,int r,int x)
 8 {
 9     if(dp[l][r][x]!=-1) return dp[l][r][x];
10     if(l==r){
11         if(x){
12           return dp[l][r][x]=1;
13         }
14         else{
15           return dp[l][r][x]=0;
16         }
17     }
18     int res=0;
19     if(x){
20         if(a[r]>a[r-1]) res=(res+f(l,r-1,1));
21         if(a[r]>a[l])   res=(res+f(l,r-1,0));
22     }
23     else{
24         if(a[l]<a[r]) res=(res+f(l+1,r,1));
25         if(a[l]<a[l+1]) res=(res+f(l+1,r,0));
26     }
27     return dp[l][r][x]=res%mod;
28 }
29 int main()
30 {
31     int N,i,j,k,s;
32     scanf("%d",&N);
33     for(i=1;i<=N;++i) scanf("%d",a+i);
34     memset(dp,-1,sizeof(dp));
35     printf("%d\n",(f(1,N,1)+f(1,N,0))%mod);
36     return 0;
37 }      

還有一道與這個類似的是 ​​http://acm.nyist.net/JudgeOnline/problem.php?pid=304​​

一道HN省賽題目，第一次沒做出來，後來補上的。

注意這道題限制了起點V，必須從這個點開始走，每一次的決策無非就是往左或是往右，隻要路過燈一定會關，因為這不消耗時間，

我們想知道[1,N]的燈全部關閉最小消耗的能源，如果我們知道了[1,N-1],和[2,N]的最小花費，是不是簡單了許多呢，我們就從這裡入手，

接着會發現即使知道了那兩個子區間，可是并不知道此時機器人是在區間的左端右端還是中間啊，沒法計算，我們不妨就令機器人每次都停在左端點或者右端點，

這樣dp[i][j][0]和dp[i][j][1]就分别表示出來了上面的兩種狀态，知道了關閉區間利用字首和求出來開啟區間的機關花費在乘上距離就能推導出新的狀态，具體細節留給大家思考，附上我的代碼。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define inf 0x3f3f3f3f
 4 int dp[1005][1005][2];
 5 int pre[1005]={0};
 6 int main()
 7 {
 8     //freopen("in.txt","r",stdin);
 9     int N,i,j,k,s;
10     int D[1005],W[1005],V;
11     while(cin>>N){
12         scanf("%d",&V);
13         for(i=1;i<=N;++i)
14         {
15           scanf("%d%d",D+i,W+i);
16           pre[i]=pre[i-1]+W[i];
17         }
18         memset(dp,inf,sizeof(dp));
19         dp[V][V][0]=dp[V][V][1]=0;
20         for(int len=2;len<=N;++len)
21         {
22             for(i=1,j=len;j<=N;++i,++j)
23             {
24                 dp[i][j][0]=min(dp[i+1][j][0]+(D[i+1]-D[i])*(pre[N]+pre[i]-pre[j]),dp[i+1][j][1]+(D[j]-D[i])*(pre[N]+pre[i]-pre[j]));
25                 dp[i][j][1]=min(dp[i][j-1][0]+(D[j]-D[i])*(pre[N]+pre[i-1]-pre[j-1]),dp[i][j-1][1]+(D[j]-D[j-1])*((pre[N]+pre[i-1]-pre[j-1])));
26             }
27 
28         }
29         printf("%d\n",min(dp[1][N][0],dp[1][N][1]));
30     }
31     return 0;
32 }      

區間dp還有一種優化的方法叫做四邊形不等式優化，具體證明參考集訓隊論文 ​​https://wenku.baidu.com/view/60f88d40336c1eb91a375d88.html​​

隻要w滿足 w(i,j)+w(i1,j1)<=w(i1,j)+w(i,j1)  (i<=i1<=j<=j1)  稱w滿足四邊形不等式

當w  滿足   w(i1,j)<=w(i,j1)  (i<=i1<=j<=j1) 稱w關于區間包含關系單調

設k=s(i,j)為w(i,j)中最優解的分割點，隻要w滿足上式，則有   s(i,j-1)<=s(i,j)<=s(i+1,j),可以降低一維的複雜度，減小了k的選擇範圍。

大家可以在一些區間dp裡嘗試使用這個優化技巧，但注意不一定題目中的w滿足四邊形不等式。

​

簡言之，區間dp能解決的問題就是通過小區間更新大區間，最後得出指定區間的最優解，這隻是初學了點皮毛，日後若發現更神秘的東西再來記下。