DP学习心得

学习心得"/>

DP学习心得

DP简介：

DP，全程动态规划，总体上的思想就是将问题分成几个局部的问题，每个局部的问题都得到最优解之后总体上也能够得到最优解。

DP与贪心算法的区别

贪心算法：只注意当前是不是最优解，没有考虑全局（并不是说没有优点）
动态规划：统揽全局，但是也不是意味着无所不能

DP使用前提

• （1）最优子结构及无后效性：原问题的最优解（或策略）包含了其子问题、更小规模问题的最优解（或策略）；无后效性指的是某阶段的状态一旦确定，则此后过程的演变不再受此前各个状态及决策的影响
• （2）重叠子问题：动态规划中涉及的子问题有可能被多次利用，因此对这些子问题只求解一次，将结果存储起来以便高效运算

动态规划算法的设计步骤

1. 分析问题，确立好最优解的结构；
2. 递归的定义最优解的值，确立好不同阶段之间的状态转移方程；
3. 根据状态转移方程，自下而上的计算每个阶段最优解的值
4. 得到一个全局最优解
5. 示意图如下：
   

例题

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最重要的就是分析问题，思考怎么将问题局部化以及状态转移方程
所以，我们在遇到这类题时，首先判断是不是能局部化，其次局部化的解怎么存储，最后怎么讲局部化的解递推出更大局部化的解。