簡(jiǎn)介
區(qū)間dp，顧名思義就是在一段區(qū)間上進(jìn)行動(dòng)態(tài)規(guī)劃。對(duì)于每段區(qū)間，他們的最優(yōu)值都是由幾段更小區(qū)間的最優(yōu)值得到，是分治思想的一種應(yīng)用，將一個(gè)區(qū)間問(wèn)題不斷劃分為更小的區(qū)間直至一個(gè)元素組成的區(qū)間，枚舉他們的組合 ，求合并后的最優(yōu)值。
算法結(jié)構(gòu)
設(shè)F[i,j]（1<=i<=j<=n）表示區(qū)間[i,j]內(nèi)的數(shù)字相加的最小代價(jià)
每次用變量k（i<=k<=j-1）將區(qū)間分為[i,k]和[k+1,j]兩段
For l:=2 to n do // 枚舉區(qū)間長(zhǎng)度
for i:=1 to n do // 枚舉區(qū)間的左端點(diǎn)
begin
j:=i+l-1; // 計(jì)算區(qū)間的右端點(diǎn),因?yàn)閰^(qū)間長(zhǎng)度和左端點(diǎn)循環(huán)嵌套枚舉，保證了[i,j]內(nèi)的所有子區(qū)間都被枚舉到
if j>n then break; // 保證了下標(biāo)不越界
for k:= i to j-1 do // 狀態(tài)轉(zhuǎn)移，去推出 f[i,j]
f[i , j]= max{f[ i,k]+ f[k+1,j]+ w[i,j] }
end;
這個(gè)結(jié)構(gòu)必須記好，這是區(qū)間動(dòng)態(tài)規(guī)劃的代碼結(jié)構(gòu)。
例題
石子合并
題目鏈接:http://acm.nyist.net/JudgeOnline/problem.php?pid=737
題意:有N堆石子排成一排，每堆石子有一定的數(shù)量?，F(xiàn)要將N堆石子并成為一堆。合并的過(guò)程只能每次將相鄰的兩堆石子堆成一堆，每次合并花費(fèi)的代價(jià)為這兩堆石子的和，經(jīng)過(guò)N-1次合并后成為一堆。求出總的代價(jià)最小值。
分析:要求n個(gè)石子歸并，我們根據(jù)dp的思想劃分成子問(wèn)題，先求出每?jī)蓚€(gè)合并的最小代價(jià)，然后每三個(gè)的最小代價(jià)，依次知道n個(gè)。
定義狀態(tài)dp[i][j]為從第i個(gè)石子到第j個(gè)石子的合并最小代價(jià)。
那么dp[i][j] = min(dp[i][k] + dp[k+1][j])
那么我們就可以從小到大依次枚舉讓石子合并，直到所有的石子都合并。
這個(gè)問(wèn)題可以用到平行四邊形優(yōu)化，用一個(gè)s[i][j]=k 表示區(qū)間 i---j 從k點(diǎn)分開(kāi)才是最優(yōu)的，這樣的話我們就可以優(yōu)化掉一層復(fù)雜度，變?yōu)镺（n^2）
代碼1(無(wú)優(yōu)化)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 210
int dp[N][N],sum[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
int a[N];sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];//因?yàn)橐蠼鈪^(qū)間和，先維護(hù)前綴和
}
memset(dp,0,sizeof(dp));
int i,j,l,k;
for(l = 2; l <= n; ++l)//枚舉區(qū)間長(zhǎng)度
{
for(i = 1; i <= n - l + 1; ++i)//枚舉區(qū)間左端點(diǎn)
{
j = i + l - 1;//根據(jù)左端點(diǎn)和區(qū)間長(zhǎng)度求區(qū)間右端點(diǎn)
if(j > n)
break;
dp[i][j] = 0x3f3f3f3f;
for(k = i; k < j; ++k)
{
dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1]);
}
}
}
printf("%d\n", dp[1][n]);
}
return 0;
}
代碼2(平行四邊形優(yōu)化)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 210
int dp[N][N],sum[N],s[N][N];
int main()
{
int n;
while(~scanf("%d",&n))
{
int a[N];sum[0]=0;
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i][i]=i;
sum[i]=sum[i-1]+a[i];//因?yàn)橐蠼鈪^(qū)間和，先維護(hù)前綴和
}
memset(dp,0,sizeof(dp));
int i,j,l,k;
for(l = 2; l <= n; ++l)//枚舉區(qū)間長(zhǎng)度
{
for(i = 1; i <= n - l + 1; ++i) //枚舉區(qū)間左端點(diǎn)
{
j = i + l - 1;//根據(jù)左端點(diǎn)和區(qū)間長(zhǎng)度求區(qū)間右端點(diǎn)
if(j > n)
break;
dp[i][j] = 0x3f3f3f3f;
for(k = s[i][j-1]; k <= s[i+1][j]; ++k)//四邊形優(yōu)化
{
if(dp[i][j]>dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1])
{
dp[i][j]=dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1];
s[i][j]=k;
}
}
}
}
printf("%d\n", dp[1][n]);
}
return 0;
}
括號(hào)匹配
題目鏈接：http://poj.org/problem?id=2955
題意:給出一串的只有‘（’ ‘）’ '[‘ ']'四種括號(hào)組成的串，讓你求解需要最少添加括號(hào)數(shù)讓串中的所有括號(hào)完全匹配。
分析：
定義dp [ i ] [ j ] 為串中第 i 個(gè)到第 j 個(gè)括號(hào)的最大匹配數(shù)目
1.如果第 i 個(gè)和第 j 個(gè)匹配,則dp [ i ] [ j ] = dp [ i+1 ] [ j-1 ] + 2 ;
2.如果第 i 個(gè)和第 j 個(gè)不匹配，枚舉中間分割點(diǎn)k(i <= k < j)
dp[ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k+1 ] [ j ] )
代碼
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int N = 120;
int dp[N][N];
int main()
{
string s;
while(cin>>s)
{
if(s=="end")
break;
memset(dp,0,sizeof(dp));
int n = s.size();
for(int len = 2;len <= n;len++)//枚舉區(qū)間長(zhǎng)度
{
for(int i = 0;i <= n - len; i++)//枚舉區(qū)間左端點(diǎn)
{
int j = i + len - 1;//確定區(qū)間右端點(diǎn)
if(j > n)
break;
if(s[i]=='('&&s[j]==')' || s[i]=='['&&s[j]==']')
dp[i][j]=dp[i+1][j-1]+2;
for(int k=i;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);//枚舉中間位置,注意j不取等號(hào)
}
}
cout<<dp[0][n-1]<<endl;
}
return 0;
}
如果要求打印路徑，即輸出匹配后的括號(hào)
題目鏈接: http://poj.org/problem?id=1141
代碼:
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 120;
int dp[N][N],pos[N][N]; /*定義pos【i】【j】表示 i 到 j 從哪兒分開(kāi)使得匹配添加括號(hào)最少，如果i和j匹配我們可以讓pos【i】【j】=-1；*/
string s;
void show(int i,int j)
{
if(i>j) return;
if(i==j)
{
if(s[i]=='('||s[i]==')') cout<<"()";
else cout<<"[]";
}
else
{
if(pos[i][j]==-1)
{
cout<<s[i];
show(i+1,j-1);
cout<<s[j];
}
else
{
show(i,pos[i][j]);
show(pos[i][j]+1,j);
}
}
}
int main()
{
while(cin>>s)
{
memset(dp,0,sizeof(dp));
int len=s.size();
for(int i=1; i<len; i++)
{
for(int j=0,k=i; k<len; j++,k++)
{
if(s[j]=='('&&s[k]==')' || s[j]=='['&&s[k]==']')
{
dp[j][k]=dp[j+1][k-1]+2;
pos[j][k]=-1;
}
for(int f=j; f<k; f++)
{
if(dp[j][f]+dp[f+1][k]>=dp[j][k])
{
dp[j][k]=dp[j][f]+dp[f+1][k];
pos[j][k]=f;
}
}
}
}
show(0,len-1);
cout<<endl;
}
return 0;
}
整數(shù)劃分
題目鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=746
題意: 給出兩個(gè)整數(shù) n , m ,要求在 n 中加入m - 1 個(gè)乘號(hào)，將n分成m段，求出這m段的最大乘積
分析: 區(qū)間dp，設(shè)dp[i][j] 表示在區(qū)間[0, i]之中，插入j個(gè)乘號(hào)可以得到的最大數(shù)
設(shè)a[i][j]為區(qū)間[i,j]所形成的數(shù)
所以 dp[i][j] = max(dp[k][j-1] * a[k + 1][i])
代碼:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long dp[25][25];
long long a[25][25];
char str[25];
int main()
{
int len, t, m;
scanf("%d", &t);
while (t--)
{
scanf("%s%d", str, &m);
len = strlen(str);
m--;
memset (a, 0, sizeof(a));
memset (dp, 0, sizeof(dp));
for (int i = 0; i < len; i++) //先對(duì)a進(jìn)行預(yù)處理，減少?gòu)?fù)雜度，a[i][j]表示第i段到第j段的數(shù)值
{
a[i][i] = str[i] - '0';
for (int j = i + 1; j < len; j++)
{
a[i][j] = a[i][j - 1] * 10 + str[j] - '0';
}
}
for (int i = 0; i < len; i++)
{
dp[i][0] = a[0][i];
}
for (int j = 1; j <= m; j++)
{
for (int i = j; i < len; i++)
{
for (int k = 0; k < i; k++)
{
dp[i][j] = max(dp[i][j], dp[k][j - 1] * a[k + 1][i]);
}
}
}
printf("%lld\n", dp[len - 1][m]);
}
return 0;
}
Halloween Costumes
題目鏈接：http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1422
題意：給你n天需要穿的衣服的樣式，每次可以套著穿衣服，脫掉的衣服就不能再穿了，問(wèn)至少要帶多少條衣服才能參加所有宴會(huì)
分析：首先我們使用dp[a][b]來(lái)表示區(qū)間 a~b 的答案，那么對(duì)于第 i 件衣服，我們有
①：如果在之后的區(qū)間內(nèi)都不再重復(fù)利用這件衣服，那么明顯 dp[i][j] = dp[i+1][j] + 1;
②：如果在之后的區(qū)間 i+1 ~ j 中存在一件衣服 k 是跟 i 一樣的，那么我們便可以考慮是不是可以將i那件衣服在k這個(gè)地方重復(fù)利用，
那么轉(zhuǎn)移方程為 dp[i][j] = min(dp[i][j] , dp[i][k-1]+dp[k+1][j])
代碼:
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[105];
int dp[105][105];
int main(void)
{
int t;
int cas = 0;
scanf("%d",&t);
while(t--)
{
cas ++;
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i++)
{
for(int j = i;j <= n;j++)
{
dp[i][j] = j-i+1;
}
}
for(int i = n-1;i >= 1;i--)
{
for(int j = i+1;j <= n;j++)
{
dp[i][j] = dp[i+1][j] + 1;
for(int k = i+1;k <= j;k++)
{
if(a[i] == a[k])
{
dp[i][j] = min(dp[i][j],dp[i][k-1] + dp[k+1][j]);
}
}
}
}
printf("Case %d: %d\n",cas,dp[1][n]);
}
return 0;
}
Cheapest Palindrome
題目鏈接:http://poj.org/problem?id=3280
題意:給你m個(gè)字符，其中有n種字符，每種字符都有兩個(gè)值，分別是增加一個(gè)這樣的字符的代價(jià)，刪除一個(gè)這樣的字符的代價(jià)，讓你求將原先給出的那串字符變成回文串的最小代價(jià)。
分析:dp[i][j]代表區(qū)間i到區(qū)間j成為回文串的最小代價(jià)，那么對(duì)于dp[i][j]有三種情況：
1、dp[i+1][j]表示區(qū)間i到區(qū)間j已經(jīng)是回文串了的最小代價(jià)，那么對(duì)于s[i]這個(gè)字母，我們有兩種操作，刪除與添加，對(duì)應(yīng)有兩種代價(jià)，dp[i+1][j]+add[s[i]],dp[i+1][j]+del[s[i]]，取這兩種代價(jià)的最小值；
2、dp[i][j-1]表示區(qū)間i到區(qū)間j-1已經(jīng)是回文串了的最小代價(jià)，那么對(duì)于s[j]這個(gè)字母，同樣有兩種操作，dp[i][j-1]+add[s[j]],dp[i][j-1]+del[s[j]]，取最小值
3、若是s[i]==s[j]，dp[i+1][j-1]表示區(qū)間i+1到區(qū)間j-1已經(jīng)是回文串的最小代價(jià)，那么對(duì)于這種情況，我們考慮dp[i][j]與dp[i+1][j-1]的大小
然后dp[i][j]取上面這些情況的最小值
代碼
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[2005][2005],add[27],del[27];
char s[2005];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)>0)
{
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
char ch[10];
int tmp1,tmp2;
scanf("%s%d%d",ch,&tmp1,&tmp2);
add[ch[0]-'a'+1]=tmp1;
del[ch[0]-'a'+1]=tmp2;
}
memset(dp,0,sizeof(dp));
for(int i=m-1;i>=1;i--)
{
for(int j=i+1;j<=m;j++)
{
dp[i][j]=min(dp[i+1][j]+add[s[i]-'a'+1],dp[i+1][j]+del[s[i]-'a'+1]);
int tmp=min(dp[i][j-1]+add[s[j]-'a'+1],dp[i][j-1]+del[s[j]-'a'+1]);
dp[i][j]=min(dp[i][j],tmp);
if(s[i]==s[j])
dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
}
printf("%d\n",dp[1][m]);
}
return 0;
}
Treats for the Cows
題目鏈接:http://poj.org/problem?id=3186
題意:只能從一個(gè)序列的左右兩端取數(shù)字，且取出的第i個(gè)數(shù)乘i,求乘積相加的最大值
分析:設(shè)dp[i][j]為取到剩余區(qū)間為[i,j]的最大值，可能由d[i+1][j]或者d[i][j-1]轉(zhuǎn)移而來(lái)
轉(zhuǎn)移方程：dp[i][j]=max(dp[i+1][j]+p[i](n+i-j),dp[i][j-1]+p[j](n+i-j)); 其中n-(j-i)是第幾次取
代碼
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int p[2010];
int dp[2010][2010];
int n;
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
dp[i][i]= n * p[i];
}
int ans=0;
for(int i=n;i>=1;i--)
for(int j=i;j<=n;j++)
{
dp[i][j]=max(dp[i+1][j]+p[i]*(n+i-j),dp[i][j-1]+p[j]*(n+i-j));
}
printf("%d\n",dp[1][n]);
}
}
