📏 子序列DP — 最长公共子序列与最长递增子序列

📖 子序列DP概览

子序列（Subsequence）是从原序列中删除若干元素（不改变顺序）得到的新序列。子序列DP的核心是：对于每个元素，考虑"选"还是"不选"。

1. 子序列 vs 子串 vs 子数组

🔬 题目一：最长公共子序列（LC 1143）

给定两个字符串，返回最长公共子序列的长度。

思路分析

代码实现

class Solution:
    def longestCommonSubsequence(self, 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]

复杂度分析

时间: O(m * n) 空间: O(m * n)

🔬 题目二：最长递增子序列（LC 300）

给定整数数组，返回最长严格递增子序列的长度。

思路分析

代码实现（O(n^2) DP版）

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

代码实现（O(n log n) 贪心+二分版）

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            lo, hi = 0, len(tails)
            while lo < hi:
                mid = (lo + hi) // 2
                if tails[mid] < num:
                    lo = mid + 1
                else:
                    hi = mid
            if lo == len(tails):
                tails.append(num)
            else:
                tails[lo] = num
        return len(tails)

复杂度分析

🔬 题目三：最长回文子序列（LC 516）

给定字符串s，返回最长回文子序列的长度。

思路分析

代码实现

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2 if length > 2 else 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]

复杂度分析

时间: O(n^2) 空间: O(n^2)

面试实战技巧

在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：

1. 解题步骤模板

2. 常见陷阱

3. 代码模板

# 通用解题模板
class Solution:
    def solve(self, input_data):
        # 1. 边界检查
        if not input_data:
            return default_value
        # 2. 初始化
        result = initial_value
        state = initial_state
        # 3. 主循环
        for item in input_data:
            state = transition(state, item)
            result = max/min/update(result, state)
        # 4. 返回结果
        return result

📝 课后练习

1. LC 392 判断子序列
2. LC 115 不同的子序列
3. LC 673 最长递增子序列的个数
4. LC 646 最长数对链

🔑 本课要点回顾

• LCS：二维DP，字符相同+1，不同取max
• LIS：O(n^2)DP或O(n log n)贪心+二分
• LPS：区间DP，两端字符匹配+2
• 子序列不要求连续
• LPS(s)=LCS(s,reverse(s))

📚 扩展阅读

• 算法导论 LCS章节
• 算法竞赛入门经典 子序列章节
• LeetCode子序列专题

⚡ 进阶专题：常见变体与扩展

每道经典题目都有丰富的变体。掌握核心模板后，灵活应对变体才是面试的真正挑战。以下列举本课相关的高频变体和扩展思路。

1. 常见题目变体

2. 面试中的沟通技巧

# 面试沟通模板
# 1. 先说思路（1-2分钟）
"这道题我想到两种解法，先说更直观的一种..."

# 2. 分析复杂度（30秒）
"时间复杂度O(n^2)，空间可以优化到O(n)"

# 3. 边写边说
"这里我定义dp[i]表示...，转移方程是..."

# 4. 主动验证
"我用示例走一遍：dp[0]=..., dp[1]=..."

# 5. 讨论优化
"空间还可以进一步优化，因为dp[i]只依赖..."

3. 代码调试检查清单

⚡ 子序列DP速查与对比

子序列问题有三个核心模型，它们的DP定义和遍历方式各不相同。

子序列问题的通用技巧