动态规划：智慧的长者

算法背后的故事：命运的阶梯

想象你站在一段有 10 级台阶的楼梯底部。你每次可以跨 1 级或 2 级台阶。到达顶层有多少种走法？

• 要到达第 10 级，你一定是从第 9 级（跨 1 步）或者第 8 级（跨 2 步）跳上来的。
• 所以，走法(10) = 走法(9) + 走法(8)。
• 但是要找到 走法(9)，你需要 走法(8) 和 走法(7)。

发现了吗？你需要 走法(8) 两次！在普通的递归方法中，你会一遍又一遍地重新计算 走法(8)。对于 100 级的楼梯，你会重复计算数十亿次。

动态规划 (Dynamic Programming) 像长者一样告诫你：“停下！第一次算出第 8 级的答案时，把它写下来。下次需要时，直接翻笔记本。”

这就是 DP 的精髓：递推关系 + 备忘录。

为什么需要它？

• 金融建模： 计算投资组合的最大回报。
• 路径规划： Google 地图在复杂的城市中寻找最短路径。
• 资源分配： 背包问题——在有限的空间内装入价值最高的物品。
• 生物信息学： 比对 DNA 序列。

算法是如何“思考”的

该算法有两种工作方式：

1. 自顶向下 (备忘录)： 从大问题开始（第 10 级）。如果你遇到一个子问题，先查笔记本。如果是空的，计算并保存。
2. 自底向上 (填表)： 从最小的问题开始（第 1 级）。一步步填表，直到达到目标。

DP 的三大支柱：

1. 最优子结构： 大问题的最优解由小问题的最优解构建而成。
2. 重叠子问题： 你会不断遇到相同的微小疑问。
3. 状态转移方程： 一个清晰的公式（如 $F(n) = F(n-1) + F(n-2)$）。

工程决策：时空权衡

DP 是终极的“以空间换时间”。

• 时间： 从 $O(2^N)$（指数级/永远算不完）降低到 $O(N^2)$ 或 $O(N)$（线性/瞬间完成）。
• 空间： 你需要 $O(N)$ 的内存来存储笔记本。
• 优化： 通常你只需要“最后两个结果”就能推导出下一个，这允许你将空间优化到 $O(1)$。

实现参考 (Python)

# 0/1 背包问题：在重量限制下获得最大价值
def knapsack(weights, values, capacity):
    n = len(values)
    # 1. 创建笔记本 (表格)
    # dp[i][w] = 使用前 i 个物品、重量限制为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # 2. 从过去构建未来 (自底向上)
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                # 抉择：拿还是不拿
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w - weights[i-1]], # 拿
                    dp[i-1][w]                               # 不拿
                )
            else:
                # 太重了，只能放弃
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

# 使用示例
vals = [60, 100, 120]
wts = [10, 20, 30]
cap = 50
print(f"最大价值: {knapsack(wts, vals, cap)}")

小结

动态规划教会我们：记忆就是力量。通过拒绝重复过去的错误（或工作），我们获得了解决看似不可能的大规模问题的能力。它提醒我们，在工程中，最优雅的解决方案往往只是一个记录了我们所有已知知识的、井井有条的笔记本。