学习笔记

Fibonacci的递归解法复杂度是指数级2^n

加入缓存，Memorization 变成O(n)

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义 自顶向下是递归+记忆化 自底向上是递推公式计算

DP的三个步骤

a. 找重复性（分治）

b.定义状态数组

c. DP 方程