06-高频算法题精讲-动态规划

本章概述

动态规划（Dynamic Programming，DP）是算法面试的重中之重，也是最具挑战性的部分。掌握动态规划不仅需要理解基本原理，更需要通过大量练习培养问题分解和状态定义的能力。本章将通过30+道经典题目，系统讲解背包问题、最长子序列、股票问题、状态机DP等核心题型。

本章涵盖：

动态规划的核心思想和解题步骤
一维、二维、多维DP的状态设计
背包问题的9种变体
最长子序列、子串、子数组问题
股票买卖的6种场景
状态机DP和博弈DP
30+道LeetCode高频真题详解

第一节：动态规划基础

1.1 什么是动态规划

动态规划的核心思想是将复杂问题分解为子问题，通过存储子问题的解来避免重复计算。

动态规划的两个关键特征：

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：递归过程中会重复计算相同的子问题

1.2 动态规划解题步骤

1. 定义状态（State）
   - dp[i] 或 dp[i][j] 表示什么含义

2. 找出状态转移方程（State Transition）
   - dp[i] 如何从之前的状态计算得出

3. 确定初始条件（Base Case）
   - dp[0] 或 dp[0][0] 的初始值

4. 确定计算顺序
   - 从前往后还是从后往前

5. 考虑空间优化
   - 是否可以用滚动数组降维

1.3 动态规划 vs 递归

记忆化递归（自顶向下）：

def fib_memo(n: int) -> int:
    """
    斐波那契数列 - 记忆化递归
    """
    memo = {}

    def helper(n):
        if n <= 1:
            return n

        if n in memo:
            return memo[n]

        memo[n] = helper(n - 1) + helper(n - 2)
        return memo[n]

    return helper(n)

# 时间复杂度: O(n)
# 空间复杂度: O(n)

动态规划（自底向上）：

def fib_dp(n: int) -> int:
    """
    斐波那契数列 - 动态规划
    """
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# 时间复杂度: O(n)
# 空间复杂度: O(n)

空间优化（滚动变量）：

def fib_optimized(n: int) -> int:
    """
    斐波那契数列 - 空间优化
    """
    if n <= 1:
        return n

    prev, curr = 0, 1

    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr

    return curr

# 时间复杂度: O(n)
# 空间复杂度: O(1)

第二节：一维动态规划

2.1 LeetCode 70. 爬楼梯（简单）

题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶？

解题思路： 状态定义：dp[i] = 到达第i阶的方法数状态转移：dp[i] = dp[i-1] + dp[i-2]

def climbStairs(n: int) -> int:
    """
    爬楼梯
    """
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# 空间优化版本
def climbStairs(n: int) -> int:
    if n <= 2:
        return n

    prev, curr = 1, 2

    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr

    return curr

# 时间复杂度: O(n)
# 空间复杂度: O(1)

2.2 LeetCode 198. 打家劫舍（中等）

题目描述： 你是一个专业的小偷，沿着一条街有若干房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

解题思路： 状态定义：dp[i] = 前i间房屋能偷到的最大金额状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

def rob(nums: list[int]) -> int:
    """
    打家劫舍
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[n - 1]

# 空间优化
def rob(nums: list[int]) -> int:
    if not nums:
        return 0

    prev, curr = 0, 0

    for num in nums:
        prev, curr = curr, max(curr, prev + num)

    return curr

# 时间复杂度: O(n)
# 空间复杂度: O(1)

2.3 LeetCode 213. 打家劫舍 II（中等）

题目描述： 所有的房屋都围成一圈，第一间房屋和最后一间房屋是相邻的。

解题思路： 分两种情况：偷第一间房（不能偷最后一间）或不偷第一间房（可以偷最后一间）。

def rob(nums: list[int]) -> int:
    """
    打家劫舍II - 环形房屋
    """
    if len(nums) == 1:
        return nums[0]

    def rob_range(start, end):
        prev, curr = 0, 0
        for i in range(start, end):
            prev, curr = curr, max(curr, prev + nums[i])
        return curr

    # 情况1: 偷第一间（不偷最后一间）
    # 情况2: 不偷第一间（可以偷最后一间）
    return max(rob_range(0, len(nums) - 1), rob_range(1, len(nums)))

# 时间复杂度: O(n)
# 空间复杂度: O(1)

2.4 LeetCode 300. 最长递增子序列（中等）

题目描述： 给定一个整数数组 nums，找到其中最长严格递增子序列的长度。

解题思路： 状态定义：dp[i] = 以nums[i]结尾的最长递增子序列长度状态转移：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]

def lengthOfLIS(nums: list[int]) -> int:
    """
    最长递增子序列 - DP解法
    """
    if not nums:
        return 0

    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)

# 时间复杂度: O(n^2)
# 空间复杂度: O(n)

优化：贪心 + 二分查找

def lengthOfLIS(nums: list[int]) -> int:
    """
    最长递增子序列 - 贪心+二分
    """
    import bisect

    tails = []  # tails[i] = 长度为i+1的递增子序列的最小末尾元素

    for num in nums:
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

# 时间复杂度: O(n log n)
# 空间复杂度: O(n)

2.5 LeetCode 322. 零钱兑换（中等）

题目描述： 给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的最少的硬币个数。

解题思路： 状态定义：dp[i] = 凑成金额i所需的最少硬币数状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)

def coinChange(coins: list[int], amount: int) -> int:
    """
    零钱兑换
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# 测试
print(coinChange([1, 2, 5], 11))  # 3 (5+5+1)
print(coinChange([2], 3))  # -1

# 时间复杂度: O(amount × len(coins))
# 空间复杂度: O(amount)

2.6 LeetCode 139. 单词拆分（中等）

题目描述： 给定一个字符串 s 和一个字符串字典 wordDict，判断 s 是否可以被空格拆分为一个或多个字典中的单词。

解题思路： 状态定义：dp[i] = s[0:i]是否可以被拆分状态转移：dp[i] = dp[j] && s[j:i] in wordDict

def wordBreak(s: str, wordDict: list[str]) -> bool:
    """
    单词拆分
    """
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

# 测试
print(wordBreak("leetcode", ["leet", "code"]))  # True
print(wordBreak("applepenapple", ["apple", "pen"]))  # True

# 时间复杂度: O(n^2)
# 空间复杂度: O(n)

第三节：二维动态规划

3.1 LeetCode 64. 最小路径和（中等）

题目描述： 给定一个包含非负整数的 m x n 网格 grid，找出一条从左上角到右下角的路径，使得路径上的数字总和最小。

解题思路： 状态定义：dp[i][j] = 到达(i,j)的最小路径和状态转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

def minPathSum(grid: list[list[int]]) -> int:
    """
    最小路径和
    """
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    # 初始化
    dp[0][0] = grid[0][0]

    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    # 填表
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

    return dp[m - 1][n - 1]

# 空间优化：只需要一行
def minPathSum(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = grid[0][0]

    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]

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

    return dp[n - 1]

# 时间复杂度: O(m × n)
# 空间复杂度: O(n)

3.2 LeetCode 62. 不同路径（中等）

题目描述： 一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，总共有多少条不同的路径？

解题思路： 状态定义：dp[i][j] = 到达(i,j)的路径数状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]

def uniquePaths(m: int, n: int) -> int:
    """
    不同路径
    """
    dp = [[1] * n for _ in range(m)]

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

    return dp[m - 1][n - 1]

# 空间优化
def uniquePaths(m: int, n: int) -> int:
    dp = [1] * n

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

    return dp[n - 1]

# 时间复杂度: O(m × n)
# 空间复杂度: O(n)

数学公式优化：

def uniquePaths(m: int, n: int) -> int:
    """
    组合数学解法：C(m+n-2, m-1)
    """
    from math import comb
    return comb(m + n - 2, m - 1)

# 时间复杂度: O(min(m, n))
# 空间复杂度: O(1)

3.3 LeetCode 5. 最长回文子串（中等）

题目描述： 给定一个字符串 s，找到 s 中最长的回文子串。

解题思路： 状态定义：dp[i][j] = s[i:j+1]是否为回文串状态转移：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

def longestPalindrome(s: str) -> str:
    """
    最长回文子串 - DP解法
    """
    if not s:
        return ""

    n = len(s)
    dp = [[False] * n for _ in range(n)]

    start, max_len = 0, 1

    # 单个字符都是回文
    for i in range(n):
        dp[i][i] = True

    # 枚举子串长度
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]

                if dp[i][j] and length > max_len:
                    start = i
                    max_len = length

    return s[start:start + max_len]

# 时间复杂度: O(n^2)
# 空间复杂度: O(n^2)

中心扩展法（更优）：

def longestPalindrome(s: str) -> str:
    """
    中心扩展法
    """
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    start, end = 0, 0

    for i in range(len(s)):
        # 奇数长度回文
        left1, right1 = expand_around_center(i, i)
        # 偶数长度回文
        left2, right2 = expand_around_center(i, i + 1)

        if right1 - left1 > end - start:
            start, end = left1, right1
        if right2 - left2 > end - start:
            start, end = left2, right2

    return s[start:end + 1]

# 时间复杂度: O(n^2)
# 空间复杂度: O(1)

3.4 LeetCode 72. 编辑距离（困难）

题目描述： 给定两个单词 word1 和 word2，计算将 word1 转换成 word2 所使用的最少操作数。可以进行插入、删除、替换三种操作。

解题思路： 状态定义：dp[i][j] = word1[0:i]转换为word2[0:j]的最少操作数状态转移：

如果word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

def minDistance(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] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )

    return dp[m][n]

# 测试
print(minDistance("horse", "ros"))  # 3
print(minDistance("intention", "execution"))  # 5

# 时间复杂度: O(m × n)
# 空间复杂度: O(m × n)

3.5 LeetCode 1143. 最长公共子序列（中等）

题目描述： 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

解题思路： 状态定义：dp[i][j] = text1[0:i]和text2[0:j]的最长公共子序列长度状态转移：

如果text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def longestCommonSubsequence(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]

# 测试
print(longestCommonSubsequence("abcde", "ace"))  # 3

# 时间复杂度: O(m × n)
# 空间复杂度: O(m × n)

空间优化：

def longestCommonSubsequence(text1: str, text2: str) -> int:
    """
    空间优化版本
    """
    m, n = len(text1), len(text2)
    # 确保text1是较短的字符串
    if m > n:
        text1, text2 = text2, text1
        m, n = n, m

    dp = [0] * (m + 1)

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

    return dp[m]

# 时间复杂度: O(m × n)
# 空间复杂度: O(min(m, n))

第四节：背包问题

4.1 0-1背包问题

问题描述： 有N个物品和容量为W的背包，每个物品有重量w[i]和价值v[i]，每个物品只能选一次，求背包能装的最大价值。

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    """
    0-1背包问题
    dp[i][w] = 前i个物品，背包容量为w时的最大价值
    """
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            # 不选第i个物品
            dp[i][w] = dp[i - 1][w]

            # 选第i个物品（如果能装下）
            if w >= weights[i - 1]:
                dp[i][w] = max(dp[i][w],
                              dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][W]

# 时间复杂度: O(n × W)
# 空间复杂度: O(n × W)

空间优化（滚动数组）：

def knapsack_01_optimized(weights: list[int], values: list[int], W: int) -> int:
    """
    0-1背包空间优化
    """
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        # 从后往前遍历，避免重复使用
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

# 时间复杂度: O(n × W)
# 空间复杂度: O(W)

4.2 LeetCode 416. 分割等和子集（中等）

题目描述： 给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解题思路： 转化为0-1背包问题：是否能从数组中选出若干数字，使其和为总和的一半。

def canPartition(nums: list[int]) -> bool:
    """
    分割等和子集
    """
    total = sum(nums)

    # 总和为奇数，无法平分
    if total % 2 == 1:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        # 从后往前遍历
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

# 测试
print(canPartition([1, 5, 11, 5]))  # True
print(canPartition([1, 2, 3, 5]))  # False

# 时间复杂度: O(n × sum/2)
# 空间复杂度: O(sum/2)

4.3 完全背包问题

问题描述： 与0-1背包类似，但每个物品可以选择无限次。

def knapsack_complete(weights: list[int], values: list[int], W: int) -> int:
    """
    完全背包问题
    """
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        # 从前往后遍历，允许重复使用
        for w in range(weights[i], W + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

# 时间复杂度: O(n × W)
# 空间复杂度: O(W)

4.4 LeetCode 518. 零钱兑换 II（中等）

题目描述： 给定不同面额的硬币和一个总金额，写一个函数来计算可以凑成总金额的硬币组合数。

解题思路： 完全背包问题的组合数版本。

def change(amount: int, coins: list[int]) -> int:
    """
    零钱兑换II - 求组合数
    """
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

# 测试
print(change(5, [1, 2, 5]))  # 4
# (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)

# 时间复杂度: O(amount × len(coins))
# 空间复杂度: O(amount)

4.5 LeetCode 279. 完全平方数（中等）

题目描述： 给定正整数 n，找到若干个完全平方数使得它们的和等于 n，返回最少数量。

解题思路： 完全背包问题，物品是完全平方数，求最少数量。

def numSquares(n: int) -> int:
    """
    完全平方数
    """
    dp = [float('inf')] * (n + 1)
    dp[0] = 0

    # 生成所有小于等于n的完全平方数
    squares = [i * i for i in range(1, int(n ** 0.5) + 1)]

    for square in squares:
        for i in range(square, n + 1):
            dp[i] = min(dp[i], dp[i - square] + 1)

    return dp[n]

# 测试
print(numSquares(12))  # 3 (4+4+4)
print(numSquares(13))  # 2 (4+9)

# 时间复杂度: O(n × sqrt(n))
# 空间复杂度: O(n)

第五节：股票买卖问题

5.1 LeetCode 121. 买卖股票的最佳时机（简单）

题目描述： 只能买卖一次，求最大利润。

解题思路： 记录当前最低价格，计算每天卖出的最大利润。

def maxProfit(prices: list[int]) -> int:
    """
    买卖股票的最佳时机
    """
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)

    return max_profit

# 时间复杂度: O(n)
# 空间复杂度: O(1)

5.2 LeetCode 122. 买卖股票的最佳时机 II（中等）

题目描述： 可以买卖多次，但必须在再次购买前出售掉之前的股票。

解题思路： 贪心算法：只要第二天价格高于今天，就在今天买入明天卖出。

def maxProfit(prices: list[int]) -> int:
    """
    买卖股票的最佳时机II - 可以多次交易
    """
    profit = 0

    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]

    return profit

# 时间复杂度: O(n)
# 空间复杂度: O(1)

动态规划解法：

def maxProfit(prices: list[int]) -> int:
    """
    DP解法
    dp[i][0] = 第i天不持有股票的最大利润
    dp[i][1] = 第i天持有股票的最大利润
    """
    n = len(prices)
    if n == 0:
        return 0

    dp = [[0] * 2 for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]

    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

    return dp[n - 1][0]

# 时间复杂度: O(n)
# 空间复杂度: O(n)

5.3 LeetCode 123. 买卖股票的最佳时机 III（困难）

题目描述： 最多可以完成两笔交易。

解题思路： 维护4个状态：第一次买入、第一次卖出、第二次买入、第二次卖出。

def maxProfit(prices: list[int]) -> int:
    """
    最多两笔交易
    """
    if not prices:
        return 0

    # 第一次买入、卖出，第二次买入、卖出的最大利润
    buy1 = buy2 = float('-inf')
    sell1 = sell2 = 0

    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)

    return sell2

# 时间复杂度: O(n)
# 空间复杂度: O(1)

5.4 LeetCode 188. 买卖股票的最佳时机 IV（困难）

题目描述： 最多可以完成 k 笔交易。

解题思路： 扩展到k次交易的状态转移。

def maxProfit(k: int, prices: list[int]) -> int:
    """
    最多k笔交易
    """
    if not prices or k == 0:
        return 0

    n = len(prices)

    # 如果k >= n//2，相当于无限次交易
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit

    # dp[i][j][0] = 第i天完成j笔交易且不持有股票
    # dp[i][j][1] = 第i天完成j笔交易且持有股票
    buy = [float('-inf')] * (k + 1)
    sell = [0] * (k + 1)

    for price in prices:
        for j in range(k, 0, -1):
            sell[j] = max(sell[j], buy[j] + price)
            buy[j] = max(buy[j], sell[j - 1] - price)

    return sell[k]

# 时间复杂度: O(n × k)
# 空间复杂度: O(k)

5.5 LeetCode 309. 最佳买卖股票时机含冷冻期（中等）

题目描述： 卖出股票后，第二天无法买入（冷冻期）。

解题思路： 维护三个状态：持有、不持有（冷冻期）、不持有（非冷冻期）。

def maxProfit(prices: list[int]) -> int:
    """
    含冷冻期的股票交易
    """
    if not prices:
        return 0

    n = len(prices)
    # hold: 持有股票
    # sold: 不持有股票且处于冷冻期
    # rest: 不持有股票且不处于冷冻期
    hold = -prices[0]
    sold = 0
    rest = 0

    for i in range(1, n):
        prev_hold = hold
        prev_sold = sold
        prev_rest = rest

        hold = max(prev_hold, prev_rest - prices[i])
        sold = prev_hold + prices[i]
        rest = max(prev_rest, prev_sold)

    return max(sold, rest)

# 时间复杂度: O(n)
# 空间复杂度: O(1)

5.6 LeetCode 714. 买卖股票的最佳时机含手续费（中等）

题目描述： 每笔交易需要支付手续费。

解题思路： 在卖出时减去手续费即可。

def maxProfit(prices: list[int], fee: int) -> int:
    """
    含手续费的股票交易
    """
    hold = -prices[0]
    cash = 0

    for i in range(1, len(prices)):
        hold = max(hold, cash - prices[i])
        cash = max(cash, hold + prices[i] - fee)

    return cash

# 时间复杂度: O(n)
# 空间复杂度: O(1)

第六节：子序列和子数组问题

6.1 LeetCode 53. 最大子数组和（中等）

题目描述： 给定一个整数数组 nums，找到一个具有最大和的连续子数组。

解题思路： Kadane算法：维护以当前位置结尾的最大子数组和。

def maxSubArray(nums: list[int]) -> int:
    """
    最大子数组和
    """
    max_sum = nums[0]
    curr_sum = nums[0]

    for i in range(1, len(nums)):
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)

    return max_sum

# 时间复杂度: O(n)
# 空间复杂度: O(1)

6.2 LeetCode 152. 乘积最大子数组（中等）

题目描述： 给定一个整数数组 nums，找出一个序列中乘积最大的连续子数组。

解题思路： 同时维护最大值和最小值（因为负数相乘可能变成最大值）。

def maxProduct(nums: list[int]) -> int:
    """
    乘积最大子数组
    """
    if not nums:
        return 0

    max_prod = min_prod = result = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_prod, min_prod = min_prod, max_prod

        max_prod = max(nums[i], max_prod * nums[i])
        min_prod = min(nums[i], min_prod * nums[i])

        result = max(result, max_prod)

    return result

# 时间复杂度: O(n)
# 空间复杂度: O(1)

6.3 LeetCode 674. 最长连续递增序列（简单）

题目描述： 给定一个未排序的整数数组，找到最长连续递增序列的长度。

解题思路： 维护当前连续递增长度。

def findLengthOfLCIS(nums: list[int]) -> int:
    """
    最长连续递增序列
    """
    if not nums:
        return 0

    max_len = 1
    curr_len = 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            curr_len += 1
            max_len = max(max_len, curr_len)
        else:
            curr_len = 1

    return max_len

# 时间复杂度: O(n)
# 空间复杂度: O(1)

6.4 LeetCode 1049. 最后一块石头的重量 II（中等）

题目描述： 有一堆石头，每次选两块石头粉碎。如果重量不同，差值形成新石头。求最后剩余石头的最小重量。

解题思路： 转化为背包问题：将石头分成两堆，使两堆重量尽可能接近。

def lastStoneWeightII(stones: list[int]) -> int:
    """
    最后一块石头的重量II
    """
    total = sum(stones)
    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True

    for stone in stones:
        for j in range(target, stone - 1, -1):
            dp[j] = dp[j] or dp[j - stone]

    # 找到最接近target的重量
    for i in range(target, -1, -1):
        if dp[i]:
            return total - 2 * i

    return 0

# 时间复杂度: O(n × sum/2)
# 空间复杂度: O(sum/2)

第七节：状态机DP

7.1 LeetCode 10. 正则表达式匹配（困难）

题目描述： 给定一个字符串 s 和一个字符规律 p，实现支持 '.' 和 '*' 的正则表达式匹配。

解题思路： 状态定义：dp[i][j] = s[0:i]是否匹配p[0:j]

def isMatch(s: str, p: str) -> bool:
    """
    正则表达式匹配
    """
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    # 空字符串匹配空模式
    dp[0][0] = True

    # 处理a*b*c*这种模式
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # *匹配0次
                dp[i][j] = dp[i][j - 2]
                # *匹配多次（如果当前字符匹配）
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

# 测试
print(isMatch("aa", "a"))  # False
print(isMatch("aa", "a*"))  # True
print(isMatch("ab", ".*"))  # True

# 时间复杂度: O(m × n)
# 空间复杂度: O(m × n)

7.2 LeetCode 312. 戳气球（困难）

题目描述： 有 n 个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。戳破第 i 个气球，可以获得 nums[i-1] * nums[i] * nums[i+1] 枚硬币。求所能获得硬币的最大数量。

解题思路： 区间DP，dp[i][j]表示戳破(i,j)开放区间所有气球能获得的最大硬币数。

def maxCoins(nums: list[int]) -> int:
    """
    戳气球
    """
    # 在两端添加1
    nums = [1] + nums + [1]
    n = len(nums)

    dp = [[0] * n for _ in range(n)]

    # 枚举区间长度
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            # 枚举最后戳破的气球
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j],
                              dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j])

    return dp[0][n - 1]

# 测试
print(maxCoins([3,1,5,8]))  # 167

# 时间复杂度: O(n^3)
# 空间复杂度: O(n^2)

第八节：树形DP

8.1 LeetCode 337. 打家劫舍 III（中等）

题目描述： 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，称之为"根"。除了根之外，每栋房子有且只有一个父房子。不能同时偷窃直接相连的两栋房子。

解题思路： 树形DP，每个节点返回两个值：选择该节点和不选择该节点的最大值。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root: TreeNode) -> int:
    """
    打家劫舍III - 树形DP
    """
    def dfs(node):
        """
        返回 (不偷当前节点的最大值, 偷当前节点的最大值)
        """
        if not node:
            return (0, 0)

        left = dfs(node.left)
        right = dfs(node.right)

        # 不偷当前节点：可以选择偷或不偷子节点
        not_rob = max(left) + max(right)

        # 偷当前节点：子节点不能偷
        rob_curr = node.val + left[0] + right[0]

        return (not_rob, rob_curr)

    return max(dfs(root))

# 时间复杂度: O(n)
# 空间复杂度: O(h)

本章总结

本章系统讲解了动态规划的核心知识：

DP解题框架：

1. 明确状态：确定dp数组的含义
2. 状态转移：找出递推关系
3. 初始条件：设置base case
4. 遍历顺序：确定计算顺序
5. 空间优化：考虑降维可能

常见DP类型总结：

类型	状态定义	典型题目	复杂度
线性DP	dp[i]	爬楼梯、打家劫舍	O(n)
区间DP	dp[i][j]	最长回文、戳气球	O(n²~n³)
背包DP	dp[i][w]	分割等和、零钱兑换	O(nW)
序列DP	dp[i]	LIS、LCS	O(n²)
树形DP	dfs返回值	打家劫舍III	O(n)
状态机DP	dp[i][state]	股票买卖	O(n×k)

优化技巧：

空间优化：滚动数组、只保留必要状态
单调队列：优化滑动窗口类问题
贪心+二分：如最长递增子序列
前缀和：快速计算区间和
记忆化搜索：自顶向下的DP

背包问题总结：

# 0-1背包（从后往前）
for i in range(n):
    for w in range(W, weight[i]-1, -1):
        dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

# 完全背包（从前往后）
for i in range(n):
    for w in range(weight[i], W+1):
        dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

股票问题状态机：

持有 ←→ 不持有
  ↓         ↓
冷冻期    交易次数

掌握动态规划需要：

理解问题的递归结构
准确定义状态
找出状态转移方程
处理边界条件
通过大量练习培养直觉

至此，本面试手册的算法部分已全部完成。建议结合实际刷题，反复练习这些经典题型，逐步提升算法能力。