当前位置：首页 > ops >正文

区间 DP 详解

ops 2025/8/30 16:23:53

区间动态规划（Interval dynamic programming，即区间 DP）常用来解决一段区间内的最优解。

区间 DP 类似于其他 DP，由多个子区间的答案合并为一个大区间的答案。

一般是先求出最小子区间的答案（如 $dp_{i,i}$ ），然后逐步进行合并得到最终答案。

区间 DP 一般可分为两种情况：

子区间 $[l, r]$ 向周围两端扩散，一般其时间复杂度为 $O(n^2)$ 。

典型例题：P2758 编辑距离。

基本步骤：
1. 枚举左端点 $l$ 。
2. 枚举右端点 $r$ 。
3. 根据状态转移方程计算从小区间转移到更大区间后的最优值。
多个小区间的答案合并为一个大区间，时间复杂度通常在 $O(n^3)$ 及以上。

典型例题：P1775 石子合并（弱化版）。
基本步骤：
1. 枚举长度 $l e n$ 。
2. 枚举左端点 $l$ 。
3. 计算出右端点 $r$ （ $r = l + l e n - 1$ ）。
4. 枚举区间的分割点 $k$ ，根据状态转移方程计算合并区间后的最优值。

例题

例题1：P2758 编辑距离

设 $dp_{i,j}$ 表示在区间 $[l, r]$ 中将 $a_i$ 转化为 $b_i$ 所消耗的最小代价。

如果 $s_l\ne s_r$ ：
$dp_{l,r}=\max\{dp_{i-1,j}+1,dp_{i,j-1}+1,dp_{i-1，j-1}+1,dp_{l,r}\}$

如果 $s_l=s_r$ ：
$dp_{l,r}=\max(dp_{l,r},dp_{l-1,r-1})$

实现

#include<bits/stdc++.h>
using namespace std;
string s,s1;
int dp[2005][2005];
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>s>>s1;s=' '+s,s1=' '+s1;fill(dp[0],dp[2005],INT_MAX);for(int i=0;i<s.size();i++){dp[i][0]=i;}for(int j=0;j<s1.size();j++){dp[0][j]=j;}for(int i=1;i<s.size();i++){for(int j=1;j<s1.size();j++){dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1,dp[i][j],(s[i]==s1[j]?dp[i-1][j-1]:INT_MAX)});}}cout<<dp[s.size()-1][s1.size()-1];return 0;
}

例题2：CF2074G Game With Triangles: Season 2

设 $dp_{l,r}$ 表示在区间 $[l, r]$ 范围的点能凑出来的最大价值。

由于图形是一个环，因此我们需要断环为链。

接下来枚举区间 $[l, r]$ ，状态转移：

$dp_{l,r}=\max\{dp_{l,r},dp_{l+1,k-1}+dp_{k+1,r-1}+a_l\times a_k\times a_r,dp_{l,k-1}+dp_{k,r},dp_{l,k}+dp_{k+1,r}\}$

最后，答案为 $max\{dp_{i,i+n-1}\}$ 。

实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,a[805],dp[805][805];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(cin>>t;t;t--){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}fill(dp[0],dp[n*2+1],0);for(int len=2;len<=n;len++){for(int l=1;l<=n*2-len+1;l++){int r=l+len-1;for(int k=l+1;k<r;k++){dp[l][r]=max({dp[l][r],dp[l+1][k-1]+dp[k+1][r-1]+a[l]*a[k]*a[r],dp[l][k-1]+dp[k][r],dp[l][k]+dp[k+1][r]});}}}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i][i+n-1]);}cout<<ans<<'\n';}return 0;
}

例题3：P1775 石子合并（弱化版）

设 $dp_{l,r}$ 表示 $[l, r]$ 范围内的石堆合并的最小代价。

由于石头堆围成一个环所以需要断环为链。

预处理出前缀和数组 $s u m$ 。

状态转移（要么维持原状，要么几堆石子合并在一块）：

$dp_{l,r}=\min(dp_{l,r},dp_{l,k}+dp_{k+1,r}+sum_r-sum_{l-1})$

实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[305],sum[305],dp[305][305];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;fill(dp[0],dp[n+1],1e18);for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i],dp[i][i]=0;}for(int len=2;len<=n;len++){for(int l=1;l<=n-len+1;l++){int r=l+len-1;for(int k=l;k<r;k++){dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);}}}cout<<dp[1][n];return 0;
}

例题4：P2858 [USACO06FEB] Treats for the Cows G/S

用区间 DP 计算最大收益。

要么拿左边那个（ $a_l$ ），要么拿右边的（ $a_r$ ）。

因此可以推出状态转移：

$dp_{l,r}=\max(dp_{l+1,r}+a_l\times(n-len+1),dp_{l,r-1}+a_r\times(n-len+1))$

实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[2005],dp[2005][2005];
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dp[i][i]=a[i]*n;}for(int len=2;len<=n;len++){for(int l=1;l<=n-len+1;l++){int r=l+len-1;dp[l][r]=max(dp[l+1][r]+a[l]*(n-len+1),dp[l][r-1]+a[r]*(n-len+1));}}cout<<dp[1][n];return 0; 
}