DP简介：
DP，全程动态规划，总体上的思想就是将问题分成几个局部的问题，每个局部的问题都得到最优解之后总体上也能够得到最优解。
DP与贪心算法的区别
贪心算法：只注意当前是不是最优解，没有考虑全局（并不是说没有优点）
动态规划：统揽全局，但是也不是意味着无所不能
DP使用前提
- （1）最优子结构及无后效性：原问题的最优解（或策略）包含了其子问题、更小规模问题的最优解（或策略）；无后效性指的是某阶段的状态一旦确定，则此后过程的演变不再受此前各个状态及决策的影响
- （2）重叠子问题：动态规划中涉及的子问题有可能被多次利用，因此对这些子问题只求解一次，将结果存储起来以便高效运算
动态规划算法的设计步骤
- 分析问题，确立好最优解的结构；
- 递归的定义最优解的值，确立好不同阶段之间的状态转移方程；
- 根据状态转移方程，自下而上的计算每个阶段最优解的值
- 得到一个全局最优解
- 示意图如下：
例题
1、斐波那契数列
- 一般的做法
- DP做法
2、01背包问题
有一个负重能力为m的背包和不同价值v[i]、不同重量w[i]的物品n件。
在不超过负重能力的前提下，从这n件物品中任意选择一个，但不能切割物品，使这些物品的价值之和最大。
假设有5个物体，重量分别为2,2,6,5,4，价值分别为6,3,5,4,6，背包的载重量为10，求装入背包的物体及其总价值。
解题思路：
01背包问题是经典的DP，每个物品都不能切割，回想DP步骤：
-
分析问题：从5个物体里面选放到背包里面，那是不是先放4个，先放3个…到先放0个，每次选择都是最优解。因为我从5个里面选择的时候已经是从4个里面选择了，并且取得最优解了。
同样，从5个物体里面选放到10的背包，那是不是先放到9的背包…到先放到0的背包。 -
递归定义最优解：
-
编写代码
-
得到最优解 m[n][c]
综上所述，DP最重要的就是分析问题，思考怎么将问题局部化以及状态转移方程
所以，我们在遇到这类题时，首先判断是不是能局部化，其次局部化的解怎么存储，最后怎么讲局部化的解递推出更大局部化的解。