33DAI：批量导入三三文档

2026-05-20T18:24:08Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 18:24的版本
第63行：		第63行：
	[[Category:动态规划]]		[[Category:动态规划]]
	[[Category:三三文档]]		[[Category:三三文档]]

33DAI：导入1个版本

2026-05-20T18:12:26Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 区间 DP ==

区间 DP 的状态定义为一个区间 <math>[l, r]</math>，通过枚举区间内的分割点 <math>k</math> 来合并两个子区间。

=== 通用模板 ===

<syntaxhighlight lang="cpp">
// 枚举区间长度 len
for (int len = 2; len <= n; len++)
for (int l = 1; l + len - 1 <= n; 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] + cost(l, k, r));
}
</syntaxhighlight>

== 石子合并 ==

有 <math>n</math> 堆石子排成一排，每次合并相邻两堆，代价为两堆石子数之和，求最小总代价。

<syntaxhighlight lang="cpp">
int a[MAXN], pre[MAXN], dp[MAXN][MAXN];

memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++)
{
dp[i][i] = 0;
pre[i] = pre[i - 1] + a[i];
}

for (int len = 2; len <= n; len++)
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
int cost = pre[r] - pre[l - 1];
for (int k = l; k < r; k++)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cost);
}
</syntaxhighlight>

== 回文串问题 ==

求最长回文子序列：

<syntaxhighlight lang="cpp">
// dp[l][r] = s[l..r] 的最长回文子序列长度
for (int i = 1; i <= n; i++)
dp[i][i] = 1;

for (int len = 2; len <= n; len++)
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
if (s[l] == s[r])
dp[l][r] = dp[l + 1][r - 1] + 2;
else
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
}
</syntaxhighlight>

[[Category:动态规划]]
[[Category:三三文档]]

12-动态规划/02-区间DP - 版本历史

33DAI：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档