1. 动态规划
百度百科:动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时， 提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。 1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
通常用凑钱的例子来说明：
假设有面值 1元，5元，11元，个数无限，现在想凑15元，怎么凑才能使钱的个数最少
- 1元 * 15个 = 15元 总共15个
- 1元 10个 + 5元 1个 = 15元 总共11个
- 1元 5个 + 5元 2个 = 15元 总共7个
- 1元 4个 + 11元 1个 = 15元 总共5个
- 5元 * 3个 = 15元 总共3个
以上是暴力列举，把所有可能都列举出来！
如果用动态规划怎么理解呢？
已知需要凑15元，已知有面值 1元，5元，11元
那么
- 15 = 1元 + f(14) 等于 1次 + f(14)次数
- 15 = 5元 + f(10) 等于 1次 + f(10)次数
- 15 = 11元 + f(4) 等于 1次 + f(4) 次数
现在要 求的是 f(14) 和 f(10) 和 f(4) 谁次数最少
简而言之，暴力解法一般都是从开头开始试，一直试到结束，动态规划是先知道结果，从结果往前推导,但代码不一定能这么写..
目前我的理解是,先不管什么分治啊什么的.. 就是已知当前这个是最优,记录它的状态,下一个(或者上一个)根据这个求得它的最优
哈哈。。 我想了两天，没想出来。。。 待我再想想这个题怎么解。。。
可参考其他的几个例子做一做