33DAI：批量导入三三文档

2026-05-20T18:24:08Z

批量导入三三文档

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

33DAI：导入1个版本

2026-05-20T18:12:25Z

导入1个版本

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

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

2026-05-20T16:50:33Z

批量导入三三文档

新页面

== 动态规划基础 ==

动态规划（DP）将问题分解为子问题，通过'''最优子结构'''和'''子问题重叠'''来高效求解。

=== DP 三要素 ===

# '''状态定义'''：<math>dp[i]</math> 表示什么
# '''状态转移方程'''：<math>dp[i]</math> 如何由前面的状态推出
# '''边界条件'''：初始状态的值

== 数字三角形 ==

从顶部出发，每次向左下或右下走一步，求到底部的最大路径和。

{| class="wikitable" style="text-align:center;"
|-
| || || 7 || ||
|-
| || 3 || || 8 ||
|-
| 8 || || 1 || || 0
|}

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

for (int j = 1; j <= n; j++)
dp[n][j] = a[n][j]; // 边界：最后一层

for (int i = n - 1; i >= 1; i--)
for (int j = 1; j <= i; j++)
dp[i][j] = a[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
</syntaxhighlight>

== 最长上升子序列（LIS） ==

求数组中最长的严格递增子序列的长度。

=== <math>O(n^2)</math> 解法 ===

<syntaxhighlight lang="cpp">
// dp[i] = 以 a[i] 结尾的最长上升子序列长度
int dp[MAXN], ans = 0;
for (int i = 1; i <= n; i++)
{
dp[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
</syntaxhighlight>

=== <math>O(n\log n)</math> 解法 ===

<syntaxhighlight lang="cpp">
vector<int> tail; // tail[i] = 长度为 i+1 的上升子序列的最小末尾值
for (int i = 1; i <= n; i++)
{
auto it = lower_bound(tail.begin(), tail.end(), a[i]);
if (it == tail.end())
tail.push_back(a[i]);
else
*it = a[i];
}
// tail.size() 即为答案
</syntaxhighlight>

== 最长公共子序列（LCS） ==

求两个字符串的最长公共子序列长度。

<syntaxhighlight lang="cpp">
// dp[i][j] = s[1..i] 与 t[1..j] 的 LCS 长度
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (s[i] == t[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
</syntaxhighlight>

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

12-动态规划/01-线性DP - 版本历史

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

33DAI：​导入1个版本

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

33DAI：批量导入三三文档

33DAI：导入1个版本

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