区间 DP

区间 DP

一、 核心思想：由小及大

区间 DP 的本质是以“区间长度”作为阶段的动态规划。

• 基本定义：状态通常定义为dp[i][j]，表示处理区间[ i , j ] [i, j][i,j]得到的最大收益或最小代价。

• 计算顺序：必须先枚举区间长度l e n lenlen，再枚举左端点i ii。

  为什么？因为计算大区间[ i , j ] [i, j][i,j]时，必须保证其内部的所有小区间（子问题）已经计算完毕。

二、 两大核心模型

在实际解题中，区间 DP 主要分为两种“套路”：

三、 关键技巧与前置知识

1. 前缀和（Optimization）：快速计算区间和sum ( i , j ) = pre [ j ] − pre [ i − 1 ] \text{sum}(i, j) = \text{pre}[j] - \text{pre}[i-1]sum(i,j)=pre[j]−pre[i−1]，将O ( n ) O(n)O(n)的求和降至O ( 1 ) O(1)O(1)。
2. 环形转链（Breaking the Circle）：* 针对“环形”石子合并，常用倍长数组（将a [ 1 … n ] a[1 \dots n]a[1…n]复制一份接在后面变成a [ 1 … 2 n ] a[1 \dots 2n]a[1…2n]）。
   • 最终结果在所有长度为n nn的区间dp[i][i+n-1]中取最值。
3. 博弈类区间 DP：* 核心在于“我拿走一部分，剩下的留给对手拿最多的”。
   • 公式：当前最大收益 = 区间总和 - 对手在剩余区间能拿的最大收益。

[P2858 USACO06FEB] Treats for the Cows G/S - 洛谷

• tips1：这是一个很明显的缩一端（剥洋葱），是很明显的区间DP
• tips2：想一下我最后一个拿出来的零食，他对答案的贡献是多少
• tips3：扩展到多个呢，比如区间[l,r]他只可能拿最左或者最优的零食

石子合并
d p [ i ] [ j ] = min ⁡ i ≤ k < j { d p [ i ] [ k ] + d p [ k + 1 ] [ j ] } + s u m [ i ] [ j ] dp[i][j] = \min_{i \leq k < j} \{dp[i][k] + dp[k + 1][j]\} + sum[i][j]dp[i][j]=i≤k<jmin​{dp[i][k]+dp[k+1][j]}+sum[i][j]
[P1040 NOIP 2003 提高组] 加分二叉树 - 洛谷

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#definewkrios::sync_with_stdio(false),cin.tie(0),cout.tie(0)constintN=31;constintINF=1e18;intc[N],dp[N][N],path[N][N];voidinit(intn){for(inti=1;i<=n;i++){path[i][i]=i;}return;}voiddfs(intl,intr){if(l>r)return;intk=path[l][r];cout<<k<<" ";dfs(l,k-1);dfs(k+1,r);}intdfs1(intl,intr){if(l==r){returndp[l][l]=c[l];}if(dp[l][r]!=0)returndp[l][r];for(intk=l;k<=r;k++){intlef=(k==l)?1:dfs1(l,k-1);intrig=(k==r)?1:dfs1(k+1,r);if(lef*rig+c[k]>dp[l][r]){dp[l][r]=lef*rig+c[k];path[l][r]=k;}}returndp[l][r];}voidsolved(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>c[i];}init(n);dfs1(1,n);cout<<dp[1][n]<<endl;dfs(1,n);}signedmain(){wkr;intT=1;//cin >> T;while(T--)solved();return0;}

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#definewkrios::sync_with_stdio(false),cin.tie(0),cout.tie(0)constintN=31;constintINF=1e18;intc[N],dp[N][N],path[N][N];voidinit(intn){for(inti=1;i<=n;i++){dp[i][i]=c[i];path[i][i]=i;}return;}voiddfs(intl,intr){if(l>r)return;intk=path[l][r];cout<<k<<" ";dfs(l,k-1);dfs(k+1,r);}voidsolved(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>c[i];}init(n);for(intlen=2;len<=n;len++){for(intl=1;l<=n;l++){if(l+len-1>n)break;intr=l+len-1;for(intk=l;k<=r;k++){intlef=(k==l)?1:dp[l][k-1];intrig=(k==r)?1:dp[k+1][r];if(lef*rig+c[k]>dp[l][r]){dp[l][r]=lef*rig+c[k];path[l][r]=k;}}}}cout<<dp[1][n]<<endl;dfs(1,n);}signedmain(){wkr;intT=1;//cin >> T;while(T--)solved();return0;}