动态规划——区间dp
什么是动态规划区间dp定义应用
例题引入题目描述输入格式输出格式样例样例输入样例输出
提示
贪心法区间dp优缺点：AC代码：代码详解三层for循环状态转移方程环形的处理
什么是动态规划
动态规划（dp）是一种通过将问题分解为子问题，并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程，动态规划可以在避免重复计算的同时找到问题的最优解，是一种高效的求解方法，常用于解决各种问题，如最短路径、背包问题、序列比对等。
区间dp
定义
区间dp是一种dp的应用，用于解决涉及区间的问题。 它将问题划分为若干个子区间，并通过定义状态和状态转移方程来求解每个子区间的最优解，最终得到整个区间的最优解。
应用
区间动态规划常用于解决一些涉及区间操作的问题，如最长公共子序列、最长回文子串等。在区间动态规划中，通常需要定义一个二维数组来表示子区间的状态，并通过填表的方式逐步求解子区间的最优解，最后得到整个区间的最优解。区间动态规划是一种高效的求解方法，可以有效地解决各种区间问题。
例题引入
石子合并是一道非常经典的区间DP的例题，很适合新手练习，下面我们看看这个题目：
题目描述
在一个圆形操场的四周摆放
N
N
N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的
2
2
2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将
N
N
N 堆石子合并成
1
1
1 堆的最小得分和最大得分。
输入格式
数据的第
1
1
1 行是正整数
N
N
N，表示有
N
N
N 堆石子。
第
2
2
2 行有
N
N
N 个整数，第
i
i
i 个整数
a
i
a_i
ai 表示第
i
i
i 堆石子的个数。
输出格式
输出共
2
2
2 行，第
1
1
1 行为最小得分，第
2
2
2 行为最大得分。
样例
样例输入
4
4 5 9 4
样例输出
43
54
提示
1
≤
N
≤
100
1\leq N\leq 100
1≤N≤100，
0
≤
a
i
≤
20
0\leq a_i\leq 20
0≤ai≤20。
贪心法
稍微想想就知道不可行，因为它每次只能合并相邻的两堆石子，用贪心的话会答案错误，因此我们考虑区间dp。
区间dp
利用区间动态规划来解决此类问题。
优缺点：
优点缺点可以求出正解时间复杂度高代码量相对较少效率低容易理解数据量大会超时
#mermaid-svg-ctCwrOlM0NikQLHI {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ctCwrOlM0NikQLHI .error-icon{fill:#552222;}#mermaid-svg-ctCwrOlM0NikQLHI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ctCwrOlM0NikQLHI .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ctCwrOlM0NikQLHI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ctCwrOlM0NikQLHI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ctCwrOlM0NikQLHI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ctCwrOlM0NikQLHI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ctCwrOlM0NikQLHI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ctCwrOlM0NikQLHI .marker.cross{stroke:#333333;}#mermaid-svg-ctCwrOlM0NikQLHI svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ctCwrOlM0NikQLHI .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-ctCwrOlM0NikQLHI text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-ctCwrOlM0NikQLHI .actor-line{stroke:grey;}#mermaid-svg-ctCwrOlM0NikQLHI .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-ctCwrOlM0NikQLHI .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-ctCwrOlM0NikQLHI #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-ctCwrOlM0NikQLHI .sequenceNumber{fill:white;}#mermaid-svg-ctCwrOlM0NikQLHI #sequencenumber{fill:#333;}#mermaid-svg-ctCwrOlM0NikQLHI #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-ctCwrOlM0NikQLHI .messageText{fill:#333;stroke:#333;}#mermaid-svg-ctCwrOlM0NikQLHI .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-ctCwrOlM0NikQLHI .labelText,#mermaid-svg-ctCwrOlM0NikQLHI .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-ctCwrOlM0NikQLHI .loopText,#mermaid-svg-ctCwrOlM0NikQLHI .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-ctCwrOlM0NikQLHI .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-ctCwrOlM0NikQLHI .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-ctCwrOlM0NikQLHI .noteText,#mermaid-svg-ctCwrOlM0NikQLHI .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-ctCwrOlM0NikQLHI .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-ctCwrOlM0NikQLHI .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-ctCwrOlM0NikQLHI .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-ctCwrOlM0NikQLHI .actorPopupMenu{position:absolute;}#mermaid-svg-ctCwrOlM0NikQLHI .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-ctCwrOlM0NikQLHI .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-ctCwrOlM0NikQLHI .actor-man circle,#mermaid-svg-ctCwrOlM0NikQLHI line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-ctCwrOlM0NikQLHI :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}
***
Sirius
你这缺点不都是同一个吗？
不不不，这不一样。
沉思了一小会
？？？
***
Sirius
确实，此题的时间复杂度高达
O
(
2
n
3
)
O(2n^3)
O(2n3)，若非这道题的数据量极小，下面的代码便会超时，那么就需要用一个特殊方法来优化一下。
AC代码：
#include
using namespace std;
int n,ans1=0x7fffffff,ans2,a[300],sum[300];
int mi[300][300],ma[300][300];
int main() {
cin >>n;
for (int i=1; i<=n; i++) {
cin >>a[i];
a[i+n]=a[i];
}
for (int i=1; i<=2*n; i++)
sum[i]=sum[i-1]+a[i];
memset(mi,0x3f,sizeof(mi));
for (int i=1; i<=2*n; i++)
mi[i][i]=0;
for (int l=1; l for (int i=1; i+l<=2*n; i++) { for (int j=i; j mi[i][i+l]=min(mi[i][i+l],mi[i][j]+mi[k+1][i+l]+sum[i+l]-sum[i-1]); ma[i][i+l]=max(ma[i][i+l],ma[i][j]+ma[k+1][i+l]+sum[i+l]-sum[i-1]); } } } for (int i=1; i ans1=min(ans1,mi[i][i+n-1]); for (int i=1; i ans2=max(ans2,ma[i][i+n-1]); cout < return 0; } 代码详解 三层for循环 第一层for循环用来分区间，我们可以选择将一个大区间分成若干个小区间，那么分的标准是什么呢？这就是第一层for循环的作用， l l l就是每次分的区间长度。第二层循环就是定义区间的左端点， j = 1 j=1 j=1，再根据 l = 2 l=2 l=2，就能确定区间为 ( 1 , 2 ) (1,2) (1,2)，即 f [ 1 ] [ 2 ] f[1][2] f[1][2]然后第三层循环就是拆分了，如上图， l = 2 l=2 l=2的时候是无法拆分了，但是 l = 3 l=3 l=3的时候是可以拆成 f [ 1 ] [ 2 ] , f [ 3 ] [ 3 ] , f [ 1 ] [ 1 ] , f [ 2 ] [ 3 ] f[1][2],f[3][3],f[1][1],f[2][3] f[1][2],f[3][3],f[1][1],f[2][3]，以及各个数据都有或没有拆分方法。 状态转移方程 区间拆分了，那么我们如何去算转移方程呢？我们将两个区间 ( 1 , 2 ) (1,2) (1,2) 和 ( 3 , 4 ) (3,4) (3,4)进行合并，那么就是1，2的代价加上3，4的代价，再加上1到4的区间和，具体的式子如下 f[1][4] = min(f[1][4],f[1][2]+f[3][4]+s[4]-s[0]); 为什么这么计算呢，因为你要知道你在求解的过程中是通过小的区间组合成较大的区间的，而你所用到的这两个小的区间 f [ 1 ] [ 2 ] + f [ 3 ] [ 4 ] f[1][2]+f[3][4] f[1][2]+f[3][4]，已经得出了最优解了，那么得出最优解需不需要花费代价呢？当然需要，所以我们需要加上那段花费，那么简单来说就是 f[1][2]+f[3][4]=s[2]-s[0]+s[4]-s[2] 因此，状态转移方程便有了： f[i][i+l]=min(f[i][i+l],f[i][k]+f[k+1][i+l]+s[i+l]-s[i-1]); 环形的处理 我们仔细阅读题目即可发现：石子是按照环形摆放的，因此区间的头和尾是能够合并的，那么如何处理呢？ 方法很简单，只需要将整一条线性的石头复制一个，让第二个的头对着第一个的尾，然后正常处理即可。 这一点在程序的很多地方可以体现出来，如： for (int i=1; i<=n; i++) { cin >>a[i]; a[i+n]=a[i]; } 、 for (int i=1; i<=2*n; i++) 以及 for (int i=1; i+l<=2*n; i++) 等等。 原文链接：
发表评论