algorithm
动态规划
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 知乎 (zhihu.com)
最少钞票数量问题引入
假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
这里使用贪心算法：首先使用最大面值，直到剩余的金额不满最大面值则依次向下，直到满足w。
但如果面额为1， 5， 11的面额纸币凑15时，贪心算法会得到错误的结果：
11+1+1+1+1 5张
但完全可以 5+5+5 3张
而贪心算法只能考虑眼前利益
那考虑其他办法，比如使用暴力算法，但这样的情况过多，时间无法承受。
重新分析：当我们第一步选用11元面值时，会面对w=4的情况:从上图= f(4)+1.同理,当我们第一步选用1,w=14:cost=f(14)+1,第一步选用5,w=10:cost = f(10)+1.
其中,cost为钞票数量,f为最少钞票数,那此时f(15) = min(以上三种cost情况)
这就是动态规划
动态规 ...