策略决策：宏伟蓝图

选择的分量

在之前的章节中，我们学习了如何组织数据（树、哈希、图）。现在，我们要问：“当路径不清晰时，我们该如何解决问题？”

生活和软件中充满了最优化问题：

• “回家的最短路径是什么？”
• “如何在这个有限的背包里装入价值最高的物品？”
• “这步棋该怎么走才是最优的？”

要回答这些问题，我们需要 策略 (Strategy)。策略是在无限的可能性空间中探索，而又不至于迷失方向的高级方法。

策略的四大支柱

在本章中，我们将探索算法思维的大师级模板：

策略的三大法则

1. 重叠子问题： 如果通往终点的路需要经过同一座桥十次，请记住那座桥！（DP 的核心）。
2. 局部 vs. 全局： 仅仅因为一个选择现在看起来不错，并不意味着它能带来最好的结局。只有当“局部最优”等于“全局最优”时，贪心算法才有效。
3. 剪枝 (Pruning)： 可能性空间是一棵树。如果你知道某个分支通向悬崖，请尽早把它砍掉。不要浪费时间探索不可能的情况。

小结

在本章中，我们将从“写代码的人”转变为“逻辑的架构师”。我们将明白，工程师工具箱中最强大的工具不是特定的语言或库，而是为正确的战斗选择正确策略的能力。

让我们从最强大（也最令人畏惧）的策略开始：动态规划。