动态规划算法入门
做梦梦见杀猪动态规划，英文描述为Dynamic programming. 是一种可以把原始问题分解为若干相关联的子解问题，并通过求取和保存子问题的解，获得原问题的解。
对于第一个特征，比较容易理解，即分解的若干子问题，包含着重复的解。举例如：斐波那契数列，F(n) = F(n-1) + F(n-2)， 求解的F(n-1)的过程中，包含着求解F(n-2)的结果。
假设当前决策结果是f[n],则最优子结构就是要让f[n-k]最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策地使用前面的局部最优解的一种性质。
爬台阶问题问题描述：有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
状态转移方程与问题分解： 根据每次能跨越的台阶数目：1级台阶或者2级台阶，因为走到N级台阶之前，人一定是处于N-1级台阶或者N-2级台阶。F（n）的走法，一定是n-1级别的台阶的所有的走法和n-2级别台阶的所有走法之和。
F（n） = F(n-1) + F(n-2); 关于状态的分解，更详细的说明，可以看这篇文章：。 作者讲的非常的通俗易懂。这么辛苦的编辑。
这类问题通常需要两个维度的变量，状态的描述比较晦涩，不容易理解，递推关系不是很直观。我自己的学习方法是牢记一个例子，这里以01背包问题为例：
问题描述：有编号分别为a,b,c,d的四件物品，它们的重量分别是2，3，4，5，它们的价值分别是3，4，5，6，现在给你个承重为8的背包，如何让背包里装入的物品具有最大的价值总和？
作者抽象的实在太好了，我觉得我都没法用语言去写出这么严格的数学公式表达和证明，这里就不赘述了。
Xi的取值为0，1 ；表示物品是否选取， i的取值为 1，2，3，4表示a,b,c,d4见物品
其中n 表示 前 n个物品，这个表述是很重要的，如果是第一次思考这个问题，很多人都会卡在这里，
第一个公式表示 n == 0 或者 m == 0 , 即物品的数量为0 或者背包的重量为0的时候，可以算是起始条件
第二个公式表示： 表示包的重量小于新增加的物品， 新增加的物品，无法装入，如下图的F(2, 2 ) 表示前两个物品，包的重量2 ， 2 (w[2] = 3)， 此时F(2,2 )= F(1 , 2) = 3;
第三个公式表示： 包的重量能够容纳w[n]，新增加的物品，这个时候，最大的价值就要在 F(n-1, m) 和F(n-1, m- Wn) + V[n]) 这两个价值中选取了。
分治法是指将问题划分成一些地子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。
动态规划适用于子问题且重叠的情况,也就是各子问题包含公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。
分治法主要在于子问题的性，比如排序算法等， 动态规划算法主要适用于处理 子问题重复性和最优子结构的的问题。