线性 DP

概念讲解

什么是 DP？

动态规划（Dynamic Programming）是一种将问题分解为子问题，通过存储子问题结果来避免重复计算的算法思想。

DP 条件

1. 最优子结构： 问题的最优解包含子问题的最优解
2. 重叠子问题： 子问题会被重复计算
3. 无后效性： 当前状态只与之前状态有关

经典问题

1. 最长上升子序列（LIS）

123456789101112int lis(vector<int>& a) {
    int n = a.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

时间复杂度：$O(n^2)$

2. 最长公共子序列（LCS）

1234567891011121314int lcs(string a, string b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[n][m];
}

时间复杂度：$O(nm)$

3. 数字三角形

12345678910int triangle(vector<vector<int>>& a) {
    int n = a.size();
    vector<vector<int>> dp = a;
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
        }
    }
    return dp[0][0];
}

考点分析

初赛考查方式

1. 程序阅读： DP 程序
2. 编程题： DP 应用

常见考点

• LIS / LCS
• 数字三角形
• 状态转移方程

例题精讲

例题 1：LIS

题目： 求 {3, 1, 4, 1, 5, 9} 的 LIS 长度。

解答：

LIS = {1, 4, 5, 9}，长度 4。

练习题

1. DP 的三个条件是什么？

2. LIS 的状态转移方程是什么？

3. LCS 的时间复杂度是多少？

易错点

⚠️ 注意：

1. 状态转移方程是关键
2. 注意初始化
3. 注意遍历顺序
4. 一维优化要注意遍历方向