序列 DP

序列 DP（Sequence DP）

序列 DP 是一类在一个或多个序列上定义状态的动态规划问题。

与线性 DP 不同，序列 DP 的状态通常表示"以某个元素结尾"或"两个序列的前缀匹配"，转移时需要考虑序列中元素之间的关系（如大小、相等、操作代价等）。

单序列：dp[i] 表示以 a[i] 结尾的最优值（如 LIS）
双序列：dp[i][j] 表示 a[0..i] 与 b[0..j] 的最优匹配（如 LCS、编辑距离）

典型问题：

问题	状态含义	时间复杂度
最长递增子序列（LIS）	以 `a[i]` 结尾的最长递增子序列长度	\(O(n^2)\) / \(O(n \log n)\)
最长公共子序列（LCS）	`a[0..i]` 与 `b[0..j]` 的最长公共子序列长度	\(O(n \cdot m)\)
编辑距离	`a[0..i]` 变为 `b[0..j]` 的最少操作数	\(O(n \cdot m)\)

最长递增子序列（LIS）

问题描述: LeetCode 300

给定整数数组 nums，找到其中最长严格递增子序列的长度。子序列可以不连续。

例如：nums = [10, 9, 2, 5, 3, 7, 101, 18] → LIS 为 [2, 3, 7, 101]，长度为 4。

动态规划

状态定义

dp[i] = 以 nums[i] 结尾的最长递增子序列长度

基础状态：dp[i] = 1（每个元素自身构成长度为 1 的子序列）

状态转移方程

\[ dp[i] = \max_{0 \le j < i,\ nums[j] < nums[i]} \{ dp[j] + 1 \} \]

对于每个 i，向前扫描所有 j < i，如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的子序列后面。

PythonC++Rust

def length_of_lis(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

int length_of_lis(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

fn length_of_lis(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut dp = vec![1; n];

    for i in 1..n {
        for j in 0..i {
            if nums[j] < nums[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }

    *dp.iter().max().unwrap()
}

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

贪心 + 二分查找

维护一个数组 tails，其中 tails[k] 表示所有长度为 k+1 的递增子序列中，末尾元素的最小值。

tails 始终保持严格递增。对于每个新元素 x：

如果 x > tails[-1]：x 可以接在最长子序列后面，直接追加
否则：用二分查找找到 tails 中第一个 ≥ x 的位置并替换

最终 tails 的长度就是 LIS 的长度。

过程演示

nums = [10, 9, 2, 5, 3, 7, 101, 18]，最终 len(tails) = 4。

元素	操作	`tails`
10	追加	`[10]`
9	替换 `tails[0]`	`[9]`
2	替换 `tails[0]`	`[2]`
5	追加	`[2, 5]`
3	替换 `tails[1]`	`[2, 3]`
7	追加	`[2, 3, 7]`
101	追加	`[2, 3, 7, 101]`
18	替换 `tails[3]`	`[2, 3, 7, 18]`

注意

tails 数组本身不是 LIS，它只是用来计算 LIS 长度的辅助结构。例如上面最终 tails = [2, 3, 7, 18]，但实际 LIS 可以是 [2, 3, 7, 101]。

PythonC++Rust

import bisect

def length_of_lis(nums: list[int]) -> int:
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

int length_of_lis(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails.size();
}

fn length_of_lis(nums: &[i32]) -> usize {
    let mut tails: Vec<i32> = Vec::new();
    for &x in nums {
        match tails.binary_search(&x) {
            Ok(pos) => tails[pos] = x,
            Err(pos) => {
                if pos == tails.len() {
                    tails.push(x);
                } else {
                    tails[pos] = x;
                }
            }
        }
    }
    tails.len()
}

时间复杂度：\(O(n \log n)\)
空间复杂度：\(O(n)\)

最长公共子序列（LCS）

问题描述: LeetCode 1143

给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。子序列可以不连续。

例如：text1 = "abcde", text2 = "ace" → LCS 为 "ace"，长度为 3。

状态定义

dp[i][j] = text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列长度

基础状态：dp[0][j] = 0，dp[i][0] = 0（空字符串与任何字符串的 LCS 为 0）

状态转移方程

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } text1[i-1] = text2[j-1] \\ \max(dp[i-1][j],\ dp[i][j-1]) & \text{if } text1[i-1] \ne text2[j-1] \end{cases} \]

直觉理解

字符相同：两个字符都纳入 LCS，长度 +1
字符不同：要么跳过 text1[i-1]，要么跳过 text2[j-1]，取较大者

DP 表格示例：text1 = "abcde", text2 = "ace"

text1 text2	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

PythonC++Rust

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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[m][n]

int longest_common_subsequence(string& text1, string& text2) {
    int m = text1.size(), n = text2.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 (text1[i - 1] == text2[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[m][n];
}

fn longest_common_subsequence(text1: &str, text2: &str) -> i32 {
    let a: Vec<char> = text1.chars().collect();
    let b: Vec<char> = text2.chars().collect();
    let (m, n) = (a.len(), b.len());
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            if a[i - 1] == b[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    dp[m][n]
}

时间复杂度：\(O(m \cdot n)\)
空间复杂度：\(O(m \cdot n)\)

空间优化

二维压缩为一维

dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。可以压缩为一维数组，但需要额外变量 prev 保存左上角 dp[i-1][j-1] 的值（因为正序遍历时它会被覆盖）。

PythonC++Rust

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)

    for i in range(1, m + 1):
        prev = 0
        for j in range(1, n + 1):
            temp = dp[j]
            if text1[i - 1] == text2[j - 1]:
                dp[j] = prev + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp

    return dp[n]

int longest_common_subsequence(string& text1, string& text2) {
    int m = text1.size(), n = text2.size();
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }

    return dp[n];
}

fn longest_common_subsequence(text1: &str, text2: &str) -> i32 {
    let a: Vec<char> = text1.chars().collect();
    let b: Vec<char> = text2.chars().collect();
    let (m, n) = (a.len(), b.len());
    let mut dp = vec![0; n + 1];

    for i in 1..=m {
        let mut prev = 0;
        for j in 1..=n {
            let temp = dp[j];
            if a[i - 1] == b[j - 1] {
                dp[j] = prev + 1;
            } else {
                dp[j] = dp[j].max(dp[j - 1]);
            }
            prev = temp;
        }
    }

    dp[n]
}

时间复杂度：\(O(m \cdot n)\)
空间复杂度：\(O(\min(m, n))\)（取较短串作为列）

编辑距离

问题描述: LeetCode 72

给定两个字符串 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作数。允许的操作：

插入一个字符
删除一个字符
替换一个字符

例如：word1 = "horse", word2 = "ros" → 最少 3 步操作。

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

状态定义

dp[i][j] = word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数

基础状态：

dp[i][0] = i（删除 word1 的前 i 个字符）

dp[0][j] = j（插入 word2 的前 j 个字符）

状态转移方程

\[ dp[i][j] = \begin{cases} dp[i-1][j-1], & \text{if } word1[i-1] = word2[j-1] \\[6pt] \min \left\{ \begin{array}{l} dp[i-1][j] + 1 \\ dp[i][j-1] + 1 \\ dp[i-1][j-1] + 1 \end{array} \right., & \text{if } word1[i-1] \ne word2[j-1] \end{cases} \]

三种操作对应的转移来源：

操作	转移来源	含义
删除 `word1[i-1]`	`dp[i-1][j] + 1`	删掉 `word1` 末尾字符，继续匹配
插入 `word2[j-1]`	`dp[i][j-1] + 1`	在 `word1` 末尾插入字符，匹配 `word2` 末尾
替换	`dp[i-1][j-1] + 1`	将 `word1` 末尾替换为 `word2` 末尾

DP 表格示例：word1 = "horse", word2 = "ros"

word1 word2	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

PythonC++Rust

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

    return dp[m][n]

int min_distance(string& word1, string& word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            }
        }
    }

    return dp[m][n];
}

fn min_distance(word1: &str, word2: &str) -> i32 {
    let a: Vec<char> = word1.chars().collect();
    let b: Vec<char> = word2.chars().collect();
    let (m, n) = (a.len(), b.len());
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 0..=m { dp[i][0] = i as i32; }
    for j in 0..=n { dp[0][j] = j as i32; }

    for i in 1..=m {
        for j in 1..=n {
            if a[i - 1] == b[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]) + 1;
            }
        }
    }

    dp[m][n]
}

时间复杂度：\(O(m \cdot n)\)
空间复杂度：\(O(m \cdot n)\)

空间优化

二维压缩为一维

与 LCS 相同，dp[i][j] 只依赖上一行和当前行的相邻值。用一维数组 + prev 变量即可。

PythonC++Rust

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))

    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j], dp[j - 1], prev) + 1
            prev = temp

    return dp[n]

int min_distance(string& word1, string& word2) {
    int m = word1.size(), n = word2.size();
    vector<int> dp(n + 1);
    iota(dp.begin(), dp.end(), 0);

    for (int i = 1; i <= m; i++) {
        int prev = dp[0];
        dp[0] = i;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1[i - 1] == word2[j - 1]) {
                dp[j] = prev;
            } else {
                dp[j] = min({dp[j], dp[j - 1], prev}) + 1;
            }
            prev = temp;
        }
    }

    return dp[n];
}

fn min_distance(word1: &str, word2: &str) -> i32 {
    let a: Vec<char> = word1.chars().collect();
    let b: Vec<char> = word2.chars().collect();
    let (m, n) = (a.len(), b.len());
    let mut dp: Vec<i32> = (0..=n as i32).collect();

    for i in 1..=m {
        let mut prev = dp[0];
        dp[0] = i as i32;
        for j in 1..=n {
            let temp = dp[j];
            if a[i - 1] == b[j - 1] {
                dp[j] = prev;
            } else {
                dp[j] = dp[j].min(dp[j - 1]).min(prev) + 1;
            }
            prev = temp;
        }
    }

    dp[n]
}

时间复杂度：\(O(m \cdot n)\)
空间复杂度：\(O(\min(m, n))\)

复杂度对比总结

问题	朴素时间	优化时间	空间	关键技巧
LIS	\(O(n^2)\)	\(O(n \log n)\)	\(O(n)\)	贪心 + 二分查找维护 `tails`
LCS	\(O(m \cdot n)\)	—	\(O(\min(m,n))\)	一维滚动 + `prev` 保存左上角
编辑距离	\(O(m \cdot n)\)	—	\(O(\min(m,n))\)	一维滚动 + `prev` 保存左上角