算法学习|动态规划|学习注意点

https://zhuanlan.zhihu.com/p/563314945

1.用空间换时间，将之前解答过的子问题答案存储为备忘录，要计算大问题的时候直接从备忘录中查找；

2.本质上主体还是一个for循环，还是遍历逻辑，只不过每次的计算都是O(1)级别的，所以时间复杂度很低O(n^2)；

3.自顶向下（记忆化递归）：递归逻辑，要解决n规模的问题，要先用相同函数解决n-i的问题，并将n-i问题最优解存储下来，然后return；

自底向上（迭代dp）：推导逻辑，先解决1规模问题并记录最优解，2规模问题用到1，3规模用到2以此类推......

4.自顶向下记忆化递归方法好想，而且可以避免计算用不到的子问题，好向，但是递归栈过深引起stack over flaw；

5.自底向上dp无需递归栈，但可能多计算东西，但是对他进行空间优化很方便。

总结与建议

• 本质是相通的：两者都运用了“记忆化/存储子问题解”的核心思想，时间复杂度在解决同一个问题时通常是相同的（如都是O(n)）。
• 自顶向下更像是 “用动态规划思想优化的递归搜索”。它让您能先用最直观的递归思路写出暴力解法，然后几乎不加思考地加入备忘录就变成了高效解法。适合面试快速实现，或当子问题空间不规则时使用。
• 自底向上是更经典的 “表格法动态规划”。它系统性更强，是算法竞赛和教科书中的标准形式。当需要空间优化，或问题要求输出所有中间状态时，它是更好的选择。

一个简单的选择策略：

1. 先尝试用递归思路定义状态和转移方程。如果很容易写出递归函数，就先用自顶向下实现。
2. 如果遇到栈溢出或需要极致优化，再将其翻译成自底向上的迭代形式。这个翻译过程（填表顺序）通常就是递归的逆过程。