圍繞幾道題說起。。石子歸并、涂色、括號序列
啥是區(qū)間動態(tài)規(guī)劃呢，我覺得似乎是指在一段區(qū)間上的dp，通過枚舉左右子區(qū)間來求出解。
那么問題來了，如何去枚舉左右子區(qū)間呢？
一般來說都是循環(huán)一個變量len，表示區(qū)間長度，然后循環(huán)左區(qū)間從開始到結(jié)尾，一般來說是1～n。
對于區(qū)間dp的話，我大致理解就是先求出小區(qū)間（部分）最優(yōu)解，然后一個又一個小區(qū)間合并成稍微大點的大區(qū)間，最后合成答案——即總區(qū)間。
所以代碼就這玩意：
for(int len=1;len<=n;len++)
{
for(int l=1,r;(r=l+len)<=n;l++)
{
//do something
for(int k=l;k<r;k++)
{
//update dp array,such as'min(dp[l][r],dp[l][i]+dp[i+1][r])'
}
}
}
所以就是這樣咯，循環(huán)一個長度，然后枚舉區(qū)間。
區(qū)間的話一定要注意是l<=k<r，不然的話[i+1][r]直接6了。。。
好像。。。區(qū)間dp就這些內(nèi)容了吧，哦對了還有平行四邊形優(yōu)化！
普通的區(qū)間dp的時間復(fù)雜度大約是O(n^3)，從三個嵌套的for就能看出來。
不過有一些區(qū)間dp可以優(yōu)化成O(n^2)，要用一個叫做“四邊形不等式”的東西進(jìn)行優(yōu)化。
大致思想就是保存枚舉的k中最優(yōu)子區(qū)間，每次可以將枚舉k時的時間復(fù)雜度去掉，所以就只剩下了長度與左區(qū)間的枚舉。
下面就是三道入門題。。。
//石子歸并
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
char in[1000];
int dp[1000][1000],n,w[1000],sum[1000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum[i]=sum[i-1]+w[i];//由于合并的是一個區(qū)間，所以記錄一下前綴和
}
for(int len=1;len<=n;len++)//循環(huán)長度
{
for(int l=1,r;(r=l+len)<=n;l++)
{
dp[l][r]=0x3fffffff;//初始化為INF
for(int i=l;i<r;i++)//枚舉中點
dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+sum[r]-sum[l-1]);//判斷區(qū)間l,r分割成兩個小區(qū)間后是否更優(yōu)
}
}
printf("%d\n",dp[1][n]);//答案
}
//bzoj1260涂色
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
char in[1000];
int dp[1000][1000];
int main()
{
scanf("%s",in+1);//方便下面dp
int n=strlen(in+1);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=i==j?1:0x3fffffff;//對于一個點的涂色次數(shù)，只能是1次
for(int len=1;len<=n;len++)//循環(huán)長度
{
for(int l=1,r;(r=l+len)<=n;l++)//生成左右區(qū)間
{
if(in[l]==in[r])//如果相等那么就可以如下這么轉(zhuǎn)移咯
{
if(len==1)dp[l][r]=1;//如果區(qū)間長度為1，也就是說l,r是相鄰的兩個格子，所以只能一筆涂上
else dp[l][r]=min(dp[l+1][r-1]+1,min(dp[l][r-1],dp[l+1][r]));
/*
否則的話說明可以從區(qū)間l,r中進(jìn)行轉(zhuǎn)移。
判斷dp[l][r]所包含的三個子區(qū)間
然后就是dp[l+1][r]跟dp[l][r-1]了。
先把最右端/最左端為起點一筆涂到另一頭，應(yīng)該是這意思吧？
*/
}
else//否則的話只能將區(qū)間l,r分割成兩個小區(qū)間然后min咯
for(int i=l;i<r;i++)
dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]);
}
}
printf("%d\n",dp[1][n]);//答案
}
//tyvj P1193 括號序列
/*
至于為什么這個dp是對的，小談一下我的個人理解。
由于區(qū)間長度len是從小到的枚舉的，所以每一輪都是從很小的單位區(qū)間開始更新，似乎可以看作bfs（霧）？
因為len是由小到大進(jìn)行枚舉，所以每一次min的時候都是從將已經(jīng)判斷好的子區(qū)間進(jìn)行min。
或許用滾雪球形容會好點？從一個小區(qū)間慢慢滾成了一個大區(qū)間？
以上就是我對于初級區(qū)間dp的理解。。。
*/
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
char in[1000];
int dp[1000][1000],n;
bool test(char a,char b)//判斷a,b是否匹配
{
if(a=='(')return b==')';
if(a=='[')return b==']';
if(a=='<')return b=='>';
if(a=='{')return b=='}';
return 0;
}
int main()
{
/*
dp[i][i]=1 若是單個括號的話只能是添加所對應(yīng)的括號完成匹配，所以為1
dp[l][r]:區(qū)間l,r的最小添加括號數(shù)量
dp[l][r]=min{n,dp[l+1][r-1](match(s[l],s[r]),dp[l][k]+dp[k+1][r]|l<=k<r}
*/
gets(in+1);//為了能夠順手的寫代碼，所以下標(biāo)從1開始
n=strlen(in+1);
while(in[n]=='\n'||in[n]=='\r')n--;
//不知道為啥gets會莫名其妙的讀入一個換行/回車，所以第一次就WA了。。。所以加上這個while判一下是否有換行，不過似乎最多就循環(huán)一次？
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int len=1;len<=n;len++)
{
for(int l=1,r;(r=l+len)<=n;l++)
{
dp[l][r]=r-l+1;//邊界，對于區(qū)間l,r一共有r-l+1個括號，所以最壞情況下需要添加r-l+1個括號，不過似乎寫成n也能A掉？好吧寫成dp[l][r]=n會快點。。。畢竟避免了加減法運算
if(test(in[l],in[r]))//如果左右兩端匹配，那么就可以進(jìn)行一次轉(zhuǎn)移
dp[l][r]=min(dp[l][r],dp[l+1][r-1]);//如果當(dāng)前區(qū)間左右都是匹配的括號的話，狀態(tài)轉(zhuǎn)移為dp[l+1][r-1]，也就是說轉(zhuǎn)移到去掉括號后的序列
for(int i=l;i<r;i++)//枚舉區(qū)間l,r中的所有區(qū)間
dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]);
}
}
printf("%d\n",dp[1][n]);//最后的結(jié)果就是dp[1][n]
}