12-动态规划/01-线性DP

动态规划基础

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

DP 三要素

1. 状态定义：[math]\displaystyle{ dp[i] }[/math] 表示什么
2. 状态转移方程：[math]\displaystyle{ dp[i] }[/math] 如何由前面的状态推出
3. 边界条件：初始状态的值

数字三角形

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

		7
	3		8
8		1		0

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]);

最长上升子序列（LIS）

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

[math]\displaystyle{ O(n^2) }[/math] 解法

// 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]);
}

[math]\displaystyle{ O(n\log n) }[/math] 解法

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() 即为答案

最长公共子序列（LCS）

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

// 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]);