**区间dp：**就是对于区间的一种动态规划，对于某个区间，它的合并方式可能有很多种，我们需要去枚举所有的方式，通常是去枚举区间的分割点，找到最优的方式(一般是找最少消耗)。
区间dp写法：（
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
状态转移函数
}
}
}
石子合并（弱化版）
问题描述：略。
转移方程：
F
(
i
,
j
)
=
m
i
n
i
≤
k
≤
j
F
(
i
,
j
)
,
F
(
i
,
k
)
+
F
(
k
+
1
,
j
)
+
∑
i
≤
z
≤
j
A
[
z
]
F(i, j ) = min_{i \leq k \leq j }{F(i,j), F(i,k) + F(k+1, j) + \sum_{i \leq z \leq j}{A[z]}}
F(i,j)=mini≤k≤jF(i,j),F(i,k)+F(k+1,j)+i≤z≤j∑A[z]
状态描述：
F(i,j)表示由i到j堆成一堆的最小代价。
边界：
F
(
i
,
j
)
=
{
0
i
f
i
=
=
j
i
n
f
i
f
i
!
=
j
F(i,j) = \begin{cases} 0 \quad if \quad i == j \\ inf \quad if \quad i != j \end{cases}
F(i,j)={0ifi==jinfifi!=j
目标：
F
(
1
,
N
)
F(1,N)
F(1,N)
代码：
void solve() {
int n; cin>>n;
vector<int> a(n+1), sum(n+1);
vector<vector<int>> f(n+1, vector<int>(n+1, INF));
for(int i = 1; i <= n; ++i) cin>>a[i], sum[i] = sum[i-1] + a[i];
for(int i = 1; i <= n; ++i) f[i][i] = 0;
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + sum[j] - sum[i-1]);
}
}
}
cout<<f[1][n];
}
石子合并
问题描述：环形石子合并，求最小和最大代价。
转移方程：
与上面类似。环状dp。
代码：
void solve() {
int n; cin>>n;
vector<int> a(n*2 + 1), sum(a);
for(int i = 1; i <= n; ++i) cin>>a[i], a[i + n] = a[i];
for(int i = 1; i <= n * 2; ++i) sum[i] = sum[i - 1] + a[i];
vector<vector<int>> fma(n*2+ 1, vector<int>(n*2 + 1)), fmi(n*2 + 1, vector<int>(n*2 + 1, INF));
for(int i = 1; i <= n*2; ++i) fmi[i][i] = 0;
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n * 2; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
fmi[i][j] = min(fmi[i][j], fmi[i][k] + fmi[k+1][j] + sum[j] - sum[i - 1]);
fma[i][j] = max(fma[i][j], fma[i][k] + fma[k+1][j] + sum[j] - sum[i - 1]);
}
}
}
int ma = -INF;
int mi = INF;
for(int i = 1; i <= n; ++i) {
ma = max(ma, fma[i][i+n-1]);
mi = min(mi, fmi[i][i+n-1]);
}
cout<<mi<<'\n'<<ma;
}
// 错误的，但是却AC了 （
void solve() {
int n; cin>>n;
vector<int> a(2 * n + 1), sum(a);
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];
}
vector<vector<int>> f(2 * n + 1, vector<int> (2 * n + 1, INF));
for(int i = 1; i <= 2* n; ++i) f[i][i] = 0;
for(int tt = 0; tt < n; ++tt) {
for(int len = 2; len <= n + tt; ++len) {
for(int i = 1; i + len - 1 <= n + tt; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + sum[j] - sum[i-1]);
}
}
}
}
int mi = INF;
for(int i = 1; i <= n; ++i) {
mi = min(mi, f[i][i+n - 1]);
}
cout<<mi<<endl;
f.assign(2 * n + 1, vector<int>(2*n+1, -INF));
for(int i = 1; i <= 2*n; ++i) f[i][i] = 0;
for(int tt = 0; tt < n; ++tt) {
for(int len = 2; len <= n + tt; ++len) {
for(int i = 1; i + len - 1 <= n + tt; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + sum[j] - sum[i-1]);
}
}
}
}
int ma = -INF;
for(int i = 1; i <= n; ++i) {
ma = max(ma, f[i][i + n - 1]);
}
cout<<ma;
}
总结
内部循环应该是从阶段到状态到决策。
阶段
→
状态
→
决策
阶段 \rightarrow 状态 \rightarrow 决策
阶段→状态→决策
对环的处理：
- 断环为链 – 将两个进行拼接。在更新时要将2*n个元素都更新，而不能只更新到前n个，否则访问到n+1~2n时会出错。
- 取模。
在环形问题中，可以选择(i+1)%n的方式，但也可以将n个元素复制一遍，变成2*n个元素，简化代码。
能量项链
问题描述：
代码：
void solve() {
int n; cin>>n;
vector<LL> a(n*2 + 1);
for(int i = 1; i <= n; ++i) cin>>a[i], a[i + n] = a[i];
vector<vector<LL>> f(2*n+1, vector<LL>(2*n+1));
for(int len = 2; len <= n + 1; ++len) {
for(int i = 1; i + len - 1 <= n * 2; ++i) {
int j = i + len - 1;
for(int k = i+1; k < j; ++k) {
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
}
}
}
LL ma = -INF;
for(int i = 1; i <= n; ++i) {
ma = max(ma, f[i][i + n]);
}
cout<<ma;
}
最大括号匹配数
问题描述：略。
转移方程：
$$
F(i,j) = \begin{cases}
if \quad s[i] 和 s[j] 是合法的一对儿括号 \quad F(i,j) = F(i+1,j-1) + 2 \
max{\sum_{i \leq k \leq j-1}F(i,k) + F(k+1,j)}
\end{cases}
$$
状态描述：
在区间[i, j]中合法序列的最多个数。
边界：无。
目标：
F(1, N)
代码：
void solve() {
char ph[N];
while(cin>>ph + 1) {
if(ph[1] == '0') break;
int n = strlen(ph + 1);
vector<vector<int>> f(n+1, vector<int>(n+1));
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
if(ph[i] == '(' && ph[j] == ')' || ph[i] == '[' && ph[j] == ']') f[i][j] = f[i+1][j-1] + 2;
for(int k = i; k < j; ++k) {
f[i][j] = max(f[i][j], f[i][k] + f[k+1][j]);
}
}
}
cout<<f[1][n]<<endl;
}
}
[P1435 IOI2000] 回文字串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题描述：略。
最长公共子序列。
代码：
void solve() {
string s1,s2; cin>>s1;
int n = s1.size();
s2 = s1;
reverse(all(s2));
s2 = " " + s2;
s1 = " " + s1;
vector<vector<int>> f(n+1, vector<int>(n+1));
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(s1[i] == s2[j]) f[i][j] = f[i-1][j-1] + 1;
else f[i][j] = max(f[i-1][j], f[i][j-1]);
}
}
cout<<n - f[n][n];
}
最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后
换句话说，只要这个子序列在B中单调递增，它就是A的子序列。 — P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
O(n * log(n))的LCS
顺序映射，用O(n * log(n))的LIS模板即可。
void solve() {
int n; cin>>n;
vector<int> b(n);
for(int i = 0; i < n; ++i) {
int t; cin>>t;
b[t-1] = i;
}
vector<int> f;
for(int i = 0; i < n; ++i) {
int a; cin>>a;
auto pos = lower_bound(all(f), b[a-1]);
if(pos == f.end()) f.push_back(b[a-1]);
else *pos = b[a-1];
}
cout<<f.size();
}
[P4342 IOI1998] Polygon - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题描述：一个多边形，点权为数，边权为操作符。删除一个边后，经相邻计算后（类似石子合并），最大值是多少。
转移方程：
KaTeX parse error: Got group of unknown type: 'internal'
状态描述：
F(i,j,k)，如果k = 1，表示在区间i到j之间合并的最小值，否则k = 0，表示在区间i到j之间合并的最大值。
边界：
F
(
i
,
j
,
k
)
=
{
−
i
n
f
i
f
k
=
0
&
&
i
!
=
j
i
n
f
i
f
k
=
1
&
&
i
!
=
j
v
a
l
(
i
,
j
)
i
f
i
=
=
j
F(i,j,k) = \begin{cases} -inf \quad if \quad k = 0 \&\& \quad i != j \\ inf \quad if \quad k = 1 \&\& \quad i != j \\ val(i,j) \quad if \quad i == j \end{cases}
F(i,j,k)=⎩
⎨
⎧−infifk=0&&i!=jinfifk=1&&i!=jval(i,j)ifi==j
目标：
m
a
x
1
≤
i
≤
≤
N
F
(
i
,
i
+
N
−
1
,
0
)
max_{1 \leq i \leq \leq N}F(i, i + N - 1,0)
max1≤i≤≤NF(i,i+N−1,0)
代码：
void solve() {
int n; cin>>n;
vector<int> a(2 * n + 1);
vector<int> op(2 * n + 1);
for(int i = 1; i <= n; ++i) {
char opt; int val;
cin>>opt>>val;
if(opt == 't') op[i-1] = 1; // 1 +
else op[i-1] = 2; // 2 *
a[i] = val;
a[n + i] = a[i];
op[i - 1 + n] = op[i - 1];
}
vector<vector<vector<int>>> f(2 * n + 1, vector<vector<int>>(2 * n + 1, vector<int>(2)));
for(int i = 1; i <= 2 * n; ++i) f[i][i][0] = f[i][i][1] = a[i];
for(int i = 1; i <= 2 * n; ++i) {
for(int j = 1; j <= 2 * n; ++j) {
if(i == j) continue;
f[i][j][1] = INF;
f[i][j][0] = -INF;
}
}
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len -1 <= 2 * n; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) {
if(op[k] == 1) {
// +
f[i][j][0] = max(f[i][j][0], f[i][k][0] + f[k+1][j][0]);
f[i][j][0] = max(f[i][j][0], f[i][k][1] + f[k+1][j][1]);
f[i][j][1] = min(f[i][j][1], f[i][k][1] + f[k+1][j][1]);
f[i][j][1] = min(f[i][j][1], f[i][k][0] + f[k+1][j][0]);
} else {
// *
f[i][j][0] = max(f[i][j][0], f[i][k][0] * f[k+1][j][0]);
f[i][j][0] = max(f[i][j][0], f[i][k][1] * f[k+1][j][1]);
f[i][j][1] = min(f[i][j][1], f[i][k][1] * f[k+1][j][1]);
f[i][j][1] = min(f[i][j][1], f[i][k][0] * f[k+1][j][0]);
}
}
}
}
int ma = -INF;
vector<int> ans;
for(int i = 1; i <= n; ++i) {
ma = max(ma, f[i][i+n-1][0]);
}
for(int i = 1; i <= n; ++i) {
if(ma == f[i][i+n-1][0]) {
ans.push_back(i);
}
}
cout<<ma<<endl;
for(auto t: ans) cout<<t<<" ";
}
总结
- 注意乘法运算性质。两个负数相乘是整数。可能现在是两块较小的数，但是经过一次操作就成特别大的数。
- 石子合并类似
凸多边形的划分 (nowcoder.com)
转移方程：
F
(
i
,
j
)
=
m
i
n
i
+
1
≤
k
≤
j
−
1
(
F
(
i
,
j
)
,
F
(
i
,
k
)
+
F
(
k
,
j
)
+
A
[
i
]
∗
A
[
j
]
∗
A
[
k
]
)
F(i,j) = min_{i + 1\leq k \leq j-1}(F(i,j), F(i,k) + F(k,j) + A[i] * A[j] * A[k])
F(i,j)=mini+1≤k≤j−1(F(i,j),F(i,k)+F(k,j)+A[i]∗A[j]∗A[k])
状态表示：
F(i,j)表示区间i到j的最小价值
边界：
F
(
i
,
i
)
=
A
[
i
]
F
(
i
,
i
+
1
)
=
0
1
≤
i
≤
2
∗
N
F(i,i) = A[i] \\ F(i,i+1) = 0 \quad 1 \leq i \leq 2 * N
F(i,i)=A[i]F(i,i+1)=01≤i≤2∗N
目标：
F
(
i
,
i
+
N
−
1
)
1
≤
i
≤
N
F(i, i + N - 1) \quad 1 \leq i \leq N
F(i,i+N−1)1≤i≤N
代码：
import math # 有高精度（
f = [[math.inf] * 154 for _ in range(154)]
n = int(input())
a = [0 for _ in range(2 * n + 12)]
arr = list(map(int, input().split()))
for i in range(1, n + 1):
a[i] = arr[i-1]
a[i + n] = a[i]
for i in range(1, 2 * n + 1):
f[i][i] = a[i]
f[i][i + 1] = 0
for len in range(2, n + 1):
for i in range(1, 2 * n - len + 1 + 1):
j = i + len - 1
for k in range(i+1,j):
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k])
mi = math.inf
for i in range(1,n + 1):
mi = min(mi, f[i][i + n - 1])
print(mi)
总结：与能量项链相同，只不过是求最小值。
P1220 关路灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
转移方程：
F
(
i
,
j
,
0
)
=
m
i
n
(
F
(
i
,
j
,
0
)
,
F
(
i
+
1
,
j
,
0
)
+
c
o
s
t
1
,
F
(
i
+
1
,
j
,
1
)
+
c
o
s
t
2
)
F
(
i
,
j
,
1
)
=
m
i
n
(
F
(
i
,
j
,
1
)
,
F
(
i
,
j
−
1
,
0
)
+
c
o
s
t
1
,
F
(
i
,
j
−
1
,
1
)
+
c
o
s
t
1
)
F(i,j,0) = min(F(i,j,0), F(i+1,j,0) + cost1, F(i+1,j,1) + cost2) \\ F(i,j,1) = min(F(i,j,1), F(i,j-1,0) + cost1, F(i,j-1,1) + cost1)
F(i,j,0)=min(F(i,j,0),F(i+1,j,0)+cost1,F(i+1,j,1)+cost2)F(i,j,1)=min(F(i,j,1),F(i,j−1,0)+cost1,F(i,j−1,1)+cost1)
状态表示：
F(i,j,k)，当k = 1时，表示移到i段最小价值，当k = 0时，表示移到j段最小价值。文章来源：https://www.toymoban.com/news/detail-638337.html
边界：
F
(
i
,
i
,
0
)
=
F
(
i
,
i
,
1
)
i
为初始位置
F(i,i,0) = F(i,i,1) \quad i为初始位置
F(i,i,0)=F(i,i,1)i为初始位置
目标：
F
(
1
,
N
)
F(1,N)
F(1,N)
代码：文章来源地址https://www.toymoban.com/news/detail-638337.html
void solve() {
int n; cin>>n; int lz; cin>>lz;
vector<LL> sit(n + 2), gl(n + 2), sum(n + 2);
vector<vector<vector<LL>>> f(n + 2, vector<vector<LL>>(n + 2, vector<LL> (2, INF)));
for(int i = 1; i <= n; ++i) cin>>sit[i]>>gl[i], sum[i] = sum[i-1] + gl[i];
f[lz][lz][1] = f[lz][lz][0] = 0;
auto cal = [&] (int l, int r) -> LL {
return sum[n] - (sum[r] - sum[l-1]);
};
for(int len = 2; len <= n; ++len) {
for(int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
for(int k = i; k < j; ++k) { // 好像没有用上
f[i][j][0] = min(f[i][j][0], f[i+1][j][0] + (sit[i+1] - sit[i]) * cal(i+1,j));
f[i][j][0] = min(f[i][j][0], f[i+1][j][1] + (sit[j] - sit[i]) * cal(i+1,j));
f[i][j][1] = min(f[i][j][1], f[i][j-1][0] + (sit[j] - sit[i]) * cal(i, j-1));
f[i][j][1] = min(f[i][j][1], f[i][j-1][1] + (sit[j] - sit[j-1]) * cal(i,j-1));
}
}
}
cout<<min(f[1][n][0], f[1][n][1]);
}
到了这里，关于区间dp 解题报告的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![动态规划——区间dp [石子合并]](https://imgs.yssmx.com/Uploads/2024/02/533080-1.png)
