动态规划入门指南

算法动态规划优化

学习路线建议

动态规划是算法中的难点，建议先掌握递归和记忆化搜索，再深入学习 DP。预计学习时间 2-3 周。

一、什么是动态规划？ 🤔

动态规划（Dynamic Programming，简称 DP）是一种通过将复杂问题分解为更小的子问题来求解的算法设计技术。

核心思想

为什么叫"动态规划"？

这个名字其实是 Richard Bellman（动态规划的创始人）为了获得政府资助而起的，因为当时"规划"听起来比"数学研究"更有吸引力 😄

实际上，动态规划与"动态"和"规划"都没有直接关系，它本质上是一种聪明的暴力搜索。

二、从斐波那契数列开始 📈

斐波那契数列是理解动态规划的最佳入门例子。

问题描述

斐波那契数列：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

数列为：0, 1, 1, 2, 3, 5, 8, 13, 21, ...

方法一：朴素递归（低效）

朴素递归实现

def fibonacci_naive(n):
    """
    朴素递归 - 时间复杂度 O(2^n)，非常慢！
    """
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# 测试
print(fibonacci_naive(10))  # 输出: 55
# 但 fibonacci_naive(50) 会运行很久...

性能问题

朴素递归存在大量重复计算。例如计算 F(5) 时，F(3) 被计算了 2 次，F(2) 被计算了 3 次。

方法二：记忆化搜索（自顶向下）

记忆化搜索实现

def fibonacci_memo(n, memo=None):
    """
    记忆化搜索 - 时间复杂度 O(n)，空间复杂度 O(n)
    """
    if memo is None:
        memo = {}
    
    # 检查是否已经计算过
    if n in memo:
        return memo[n]
    
    # 基本情况
    if n <= 1:
        return n
    
    # 计算并存储结果
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# 测试
print(fibonacci_memo(50))  # 瞬间完成！

方法三：动态规划（自底向上）

动态规划实现

def fibonacci_dp(n):
    """
    动态规划 - 时间复杂度 O(n)，空间复杂度 O(n)
    """
    if n <= 1:
        return n
    
    # 创建 DP 表
    dp = [0] * (n + 1)
    dp[1] = 1
    
    # 填表
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# 测试
print(fibonacci_dp(50))  # 输出: 12586269025

方法四：空间优化

python

def fibonacci_optimized(n):
    """
    空间优化的动态规划 - 时间复杂度 O(n)，空间复杂度 O(1)
    """
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1

性能对比

O(2ⁿ)

朴素递归

O(n)

记忆化/DP

O(1)

空间优化

动态规划效率提升100%

三、动态规划解题框架 📐

掌握动态规划的关键是遵循一个系统化的解题框架。

四步解题法

定义状态

明确 dp[i] 或 dp[i][j] 表示什么含义。

状态转移方程

找出大问题与小问题之间的关系。

边界条件

确定初始值和特殊情况。

计算顺序

决定是自顶向下还是自底向上。

实战示例：爬楼梯问题

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

问题分析

- 到达第 n 阶的方法数 = 到达第 n-1 阶的方法数 + 到达第 n-2 阶的方法数 - 因为最后一步可以是爬 1 阶或 2 阶 - 这就是斐波那契数列！

爬楼梯问题解决方案

def climb_stairs(n):
    """
    爬楼梯问题 - 动态规划解法
    """
    if n <= 2:
        return n
    
    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(5))  # 输出: 8

四、经典动态规划问题 🏆

1. 背包问题

0-1 背包问题：给定 n 个物品，每个物品有重量和价值，在不超过背包容量的前提下，如何选择物品使总价值最大？

0-1 背包问题

def knapsack_01(weights, values, capacity):
    """
    0-1 背包问题
    :param weights: 物品重量列表
    :param values: 物品价值列表
    :param capacity: 背包容量
    :return: 最大价值
    """
    n = len(weights)
    # dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            # 不选第 i 个物品
            dp[i][j] = dp[i - 1][j]
            
            # 选第 i 个物品（如果放得下）
            if j >= weights[i - 1]:
                dp[i][j] = max(dp[i][j], 
                              dp[i - 1][j - weights[i - 1]] + values[i - 1])
    
    return dp[n][capacity]

# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity))  # 输出: 10

2. 最长公共子序列（LCS）

问题：给定两个字符串，找到它们最长的公共子序列的长度。

python

def longest_common_subsequence(text1, text2):
    """
    最长公共子序列
    """
    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(longest_common_subsequence("ABCBDAB", "BDCABA"))  # 输出: 4

3. 编辑距离

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

编辑距离

def min_distance(word1, word2):
    """
    编辑距离（Levenshtein Distance）
    """
    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(min_distance("horse", "ros"))  # 输出: 3

五、动态规划 vs 其他方法 ⚖️

方法	时间复杂度	空间复杂度	适用场景
暴力搜索	指数级	O(n)	小规模问题
贪心算法	O(n log n)	O(1)	局部最优即全局最优
动态规划	多项式级	O(n²)	重叠子问题+最优子结构
分治法	O(n log n)	O(log n)	子问题独立

选择策略

如果问题具有最优子结构和重叠子问题 → 动态规划
如果贪心选择性质成立 → 贪心算法（更高效）
如果子问题独立 → 分治法

六、常见误区与技巧 💡

误区一：所有问题都能用 DP

不是所有问题都适合动态规划。只有同时满足以下两个条件才适用：

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：相同的子问题被重复计算

如果不满足这两个条件，使用 DP 反而会增加复杂度。

技巧一：状态压缩

当 DP 只依赖前一行或前几行时，可以使用滚动数组优化空间。

例如斐波那契数列，只需要保存前两个值，空间从 O(n) 降到 O(1)。

技巧二：记忆化 vs 表格法

记忆化搜索：代码更直观，只计算需要的状态
表格法：避免递归开销，更容易优化

实际应用中，优先使用记忆化搜索，遇到性能瓶颈再改为表格法。

技巧三：画图辅助理解

对于复杂的 DP 问题，画出 DP 表格能帮助理解状态转移过程。

特别是二维 DP，可视化填表过程能发现规律和优化空间。

七、学习路径建议 🗺️

第1周

基础入门

掌握斐波那契、爬楼梯等简单 DP 问题，理解基本概念。

第2周

一维 DP

学习打家劫舍、买卖股票等问题，熟练一维状态定义。

第3周

二维 DP

攻克背包问题、编辑距离等经典二维 DP 问题。

第4周+

进阶提升

挑战区间 DP、树形 DP、状态压缩 DP 等高级主题。

八、总结与展望 🎯

动态规划是算法学习中的重要里程碑，掌握它将大幅提升你解决复杂问题的能力。

✅ 理解最优子结构和重叠子问题
✅ 掌握记忆化搜索和表格法
✅ 熟练运用四步解题框架
✅ 完成至少 20 道 DP 练习题
✅ 能够识别适合 DP 的问题