动态规划 (Dynamic Programming)

动态规划 (DP) 是一种通过将复杂问题分解为重叠子问题并存储子问题的解，从而避免重复计算的算法技术。

核心思想

DP = 递归 + 记忆化 (Memoization)

1. 重叠子问题: 不同的状态计算过程中需要用到相同的子问题结果。
2. 最优子结构: 问题的最优解包含其子问题的最优解。
3. 状态转移方程: 描述问题规模如何缩小的公式。

入门案例：爬楼梯

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

分析：

• 第 \(n\) 阶只能从 \(n-1\) 阶走 1 步上来，或者从 \(n-2\) 阶走 2 步上来。
• 所以：\(f(n) = f(n-1) + f(n-2)\)。
• 这不就是斐波那契数列吗？是的！

方法 1: 记忆化搜索 (自顶向下)

memo = {}

def climb_stairs_memo(n):
    if n == 1: return 1
    if n == 2: return 2

    if n in memo:
        return memo[n]

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

方法 2: 表格法 (自底向上，推荐)

我们建立一个 dp 数组，dp[i] 表示到达第 \(i\) 阶的方法数。

def climb_stairs_dp(n):
    if n == 1: return 1
    # 初始化 DP 表
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

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

    return dp[n]

print(climb_stairs_dp(5)) # 8

进阶案例：最长递增子序列 (LIS)

题目：给定一个无序整数数组，找到其中最长上升子序列的长度。 例如：[10, 9, 2, 5, 3, 7, 101, 18] -> 最长子序列是 [2, 3, 7, 101]，长度 4。

定义状态： dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。

状态转移： 对于每个 i，遍历它前面的所有 j < i： 如果 nums[i] > nums[j]，说明 nums[i] 可以接在 nums[j] 后面。 dp[i] = max(dp[i], dp[j] + 1)

def length_of_lis(nums):
    if not nums: return 0

    # 初始化：每个元素自身长度至少为 1
    dp = [1] * len(nums)

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

    return max(dp)

DP 解题四步法

1. 定义 DP 数组含义: dp[i] 到底代表什么？
2. 确定递推公式: dp[i] 怎么由 dp[i-1] 推导出来？
3. 初始化: dp[0] 是多少？
4. 遍历顺序: 从前向后还是从后向前？

本章小结

动态规划是算法中最难的部分之一。关键在于如何定义状态。一旦状态定义好了，转移方程通常就顺理成章了。

---

下一章：背包问题