动态规划（DP）

本课程是从少年编程网转载的课程，目标是向中学生详细介绍计算机比赛涉及的编程语言，数据结构和算法。编程学习最好使用计算机，请登陆 www.3dian14.org (免费注册，免费学习)。

本月7月13日上午，公安部在北京召开新闻发布会，介绍聊城“1997.9.21”郭新振（电影《失孤》被拐儿童原型）被拐卖案侦破情况。破案过程中生物技术的力量功不可没。 通过DNA序列比对来确定血亲关系，是生物信息学的一个应用，而背后的算法的基础叫做动态规划（DP）。

DP是个比较难的概念。

我们从动态规划中大名鼎鼎的背包问题开始说起。。。

---

对于背包问题，最简单的是暴力解法，尝试跟着可能的组合：

也许你一眼看出了答案。其实是你大脑偷偷做了各种排列组合。

下面主角登场了——DP

动态规划的基本原则是：先接近小问题，再逐步解决类似的大问题

---

我们用表格来记录小问题，先完成一个亿点点的小目标：

我们来完成生命中第一个DP问题：

动态有点大，我裁成了4份：

   

         

            

我们完成了第一个DP问题。总结一下：表格的每一个格子代表了一个DP小问题的最优解。 在往下逐步填满小格子时， 我们不断的在重用已经解决的小问题的答案。或者说把新的问题分解为已经解决的小问题。

问题1：  如果又发现一个仙品，怎么办？

如果再来一个物品，我们只要给表格再加一行就好：

问题2：如果仙品的重量不是整数，怎么办？

需要重新设计表格，因为我们需要包含更多的小问题。