Dynamic Programming

什么是DP

https://www.quora.com/What-does-a-state-represent-in-terms-of-Dynamic-Programming

本质上是用空间换时间，解决原问题需要先解决子问题，如果子问题有很多是重复的，那么可以缓存答案避免重复计算子问题。

所以一个问题是不是DP关键是有没有和如何解决重复子问题

DP方法分类

What is Dynamic Programming?

Dynamic Programming Methods

1. Top-down with Memoization

2. Bottom-up with Tabulation

2种，从上往下 和 从下往上，这个里面以斐波那契数列为例说的比较清楚。

1. Top-down with Memoization

这个就是在递归时增加缓存，已经递归计算过的问题直接取缓存并返回，所以不必重复递归计算。

2. Bottom-up with Tabulation

迭代方式+缓存。