Dynamic Programming
Big idea, hard, yet simple
- Powerful algorithmic design technique
- Large class of seemingly exponential problems have a polynomial solution (“only”)
via DP
- Particularly for optimization problems (min / max) (e.g., shortest paths)
<aside>
💡 * DP ≈ “controlled brute force”
- DP ≈ recursion(subproblems) + re-use(memorization) + guessing
</aside>
动态规划的名字就是为了酷
Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths
Fibonacci
递归
记忆化查找
DP = Recursion+ memorization
总时间 = 子问题数量*每个子问题用时
Bottom-up DP 自下而上
