线性动态规划（施工中）

zxcvbnm

2025-10-25 21:08:04

发布于：上海

5阅读

0回复

0点赞

C++ 线性动态规划（Linear DP）整理

[TOC]

一、基本概念

定义：
- 线性 DP 是动态规划的一种形式，其状态转移沿着线性结构（如数组、字符串、序列等）展开，状态通常由一维或二维表示，且每个状态的转移仅依赖于其前驱状态。
核心要素：
- 状态定义：明确 dp[i] 或 dp[i][j] 的含义（如以第 i 个元素结尾的子问题的解）。
- 状态转移方程：描述状态之间的递推关系（如 dp[i] = max(dp[i-1], dp[i-2] + a[i])）。
- 边界条件：初始化初始状态（如 dp[0] = 0）。
特点：
- 时间复杂度通常为 O(n) 或 O(n²)，空间复杂度可优化为 O(1) 或 O(n)。
- 问题具有明显的“阶段”特性，每个阶段的状态仅由前一阶段决定。

二、常见优化方法

空间压缩（滚动数组）：
- 当状态转移仅依赖前几个状态时，用固定大小的数组或变量代替完整数组。
- 示例：斐波那契数列 dp[i] = dp[i-1] + dp[i-2] → 只需两个变量 prev 和 curr。
单调队列优化：
- 适用于状态转移为 dp[i] = min/max(dp[j] + cost(j)) 且 j 在滑动窗口内的情况。
- 示例：滑动窗口最大值问题，时间复杂度从 O(n²) 降至 O(n)。
前缀和优化：
- 当状态转移需要累加区间和时，用前缀和数组快速计算。
- 示例：子数组和问题，sum[i:j] = prefix[j] - prefix[i-1]。

三、常见问题分类与模型

模型	问题示例	状态定义	转移方程
最长递增子序列 (LIS)	求序列中最长的递增子序列长度	`dp[i]`：以 `a[i]` 结尾的 LIS 长度	`dp[i] = max((dp[i], dp[j] + 1))`（`j < i` 且 `a[j] < a[i]`）
[最长公共子序列 (LCS)](#2、最长公共子序列 (LCS))	求两个序列的最长公共子序列	`dp[i][j]`：`a[0:i]` 和 `b[0:j]` 的 LCS 长度	`dp[i][j] = dp[i-1][j-1] + 1`（若 `a[i] == b[j]`）
背包问题	0-1 背包、完全背包	`dp[i][w]`：前 `i` 个物品装入容量 `w` 的最大价值	`dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i)`
最大子数组和	求连续子数组的最大和	`dp[i]`：以 `a[i]` 结尾的最大子数组和	`dp[i] = max(a[i], dp[i-1] + a[i])`
编辑距离	字符串的最小编辑次数（增删改）	`dp[i][j]`：将 `a[0:i]` 转为 `b[0:j]` 的最小操作数	`dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)`
路径计数	网格中从起点到终点的路径数	`dp[i][j]`：到达 `(i, j)` 的路径数	`dp[i][j] = dp[i-1][j] + dp[i][j-1]`

1、最长递增子序列（LIS）

1.1 题面

1.2 思路

问题分析

最长上升子序列（LIS）要求找到序列中严格递增的子序列的最大长度。关键在于子序列的元素可以非连续，但必须严格递增。
动态规划思路

最优子结构：以某个元素结尾的 LIS 长度，可以通过其前面的更小元素的 LIS 长度推导而来。

状态定义：定义 dp[i] 表示以第 i 个元素结尾的 LIS 长度。

初始状态：每个元素自身构成长度为 1 的子序列，因此 dp[i] 初始化为 1。

状态转移：对于每个元素 a[i]，遍历其前面的所有元素 a[j]（j < i），若 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)。

1.3 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> dp(n, 1); 
    int max_len = 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);
            }
        }
        max_len = max(max_len, dp[i]);
    }

    cout << max_len << endl;
    return 0;
}

2、最长公共子序列 (LCS)

2.1 题面

2.2 思路

问题分析

最长公共子序列（LCS）要求找到两个字符串中顺序一致但不必连续的最长子序列。
动态规划思路

状态定义：dp[i][j] 表示字符串 X 前 i 个字符和字符串 Y 前 j 个字符的 LCS 长度。

状态转移：
- 若 X[i-1] == Y[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1（当前字符匹配，长度加 1）。
- 否则，LCS 的长度继承自以下两种情况的最大值：
  - 不包含 X[i-1]：取 dp[i-1][j]（X 的前 i-1 字符与 Y 的前 j 字符的 LCS 长度）。
  - 不包含 Y[j-1]：取 dp[i][j-1]（X 的前 i 字符与 Y 的前 j-1 字符的 LCS 长度）。
  即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
初始状态：dp[0][j] 和 dp[i][0] 均为 0（空字符串无公共子序列）。

2.3 代码实现

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    string X, Y;
    cin >> X >> Y;
    int m = X.size(), n = Y.size();
    
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i-1] == Y[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    cout << dp[m][n] << endl;
    return 0;
}

3、背包问题

（1）题面

（2）思路

（3）代码实现

4、最大子数组和

4.1 题面

4.2 思路

问题本质分析

目标：寻找数组中连续的一段元素，使得它们的和最大。

关键限制：子段必须连续且非空，数组元素包含正负数。
动态规划思路

观察规律：假设我们已经知道以第 i-1 个元素结尾的最大子段和 dp[i-1]，那么以第 i 个元素结尾的最大子段和有两种可能：

1.单独以 a[i] 开头：dp[i] = a[i]。

2.接续前一个子段：dp[i] = dp[i-1] + a[i]。

选择最优解：每一步选择是否将当前元素加入之前的子段时，若之前的子段和是负数，则直接放弃前面的子段，从当前元素重新开始。负数的前缀和会降低后续子段的总和，因此当 dp[i-1] + a[i] < a[i] 时，直接以 a[i] 作为新起点。取两者中较大值，即 dp[i] = max(a[i], dp[i-1] + a[i])。

全局最大值：遍历过程中，不断记录所有 dp[i] 中的最大值。

4.3 代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> dp(n, 0);
    int global_max = a[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = max(a[i], dp[i-1] + a[i]); 
        global_max = max(global_max, dp[i]);
    }
    cout << global_max;
    return 0;
}