入门
ref：https://www.zhihu.com/question/23995189
例子
在身上带着不同数额的钞票，目标是凑出来某个金额w，使用尽量少的钞票
- 如果用贪心算法，实际上就是尽快让w变得更小，有更大面值的就用更大面值的钞票
- 但是如果换了一组其他的钞票面值，可能就会出现问题（比如 1，5，11凑15）
- 因为在贪心算法里面，需要先把15降成4，再把4降下来，但是降4的成本很高，需要4张1
- 在考虑的时候鼠目寸光，只考虑了眼前的情况，没有考虑后续的发展
- 如果开始列举，其实这个问题就会变成
接下来需要凑出来n，需要f(n)张钞票 - 这时候，凑15其实就变成了三个情况
- f(4) + 1
- f(10) + 1
- f(14) +1
- 可以发现实际上f(15)只和这三个值有关系，也就是只和n-1，n-5，n-11有关系
f(n) = min(f(n-1),f(n-5),f(n-11))+1- 这是一个可以迭代的式子对不对！
- 并不关心到底是怎么凑出来的，反正只关心f(w)的值
- 在代码实现上面，只需从小到大对比所有的cost就可以了，也就是对比新的方案的cost是不是会比以前的方案小。注意在求的时候可能会需要i-1/-5/-11的值，所以要把从头到尾的值都记录下来
- 比如要求凑15块钱，会先考虑15比1大，那么把1块拿出来，看看取14块钱的时候需要的步骤是多少，然后把5块拿出来，看看比拿1块差多少，最后拿11，看看和之前的cost差多少
区别
- dp和贪心算法的区别就在于，dp会分别算出不同策略的代价，而贪心算法包含着冗余的信息（到底怎么使用）
- 所以就是求出来fn -> 得到求fn需要的fc -> 求fc，不停的循环
- 也就是把一个问题拆成了不同的子问题
概念
- 后无效性
- 一旦fn确定，我们就不需要知道怎么得到的fn了，只在后面直接用就可以了
- 最优子结构
- 在得到fn的时候本身得到的就是最优的fn了，所以在用的时候才可以放心的用
- 一旦问题可以拆成子问题，并且满足上面的两个概念，就可以用dp解了
为什么快
- dp和贪心都是在空间里寻找最优解，但是dp在找解的时候已经找到了子问题的最优解，也就是说他已经把子问题里面不可能的状态排除掉了
算法设计
- 把现在面对的局面看做x
- 对于x，需要求得答案是fx，目标是求出来fT，找出x和哪些局面p有关，写出一个状态专业方程，来求fp到fx的关系
- 也就是考虑现在我是谁，和我从哪里来（或者我到哪里去）