动态规划（DP）
本课程是从少年编程网转载的课程，目标是向中学生详细介绍计算机比赛涉及的编程语言，数据结构和算法。编程学习最好使用计算机，请登陆 www.3dian14.org (免费注册，免费学习)。
本月7月13日上午，公安部在北京召开新闻发布会，介绍聊城“1997.9.21”郭新振（电影《失孤》被拐儿童原型）被拐卖案侦破情况。破案过程中生物技术的力量功不可没。 通过DNA序列比对来确定血亲关系，是生物信息学的一个应用，而背后的算法的基础叫做动态规划（DP）。
DP是个比较难的概念。
我们从动态规划中大名鼎鼎的背包问题开始说起。。。
对于背包问题，最简单的是暴力解法，尝试跟着可能的组合：
也许你一眼看出了答案。其实是你大脑偷偷做了各种排列组合。
下面主角登场了——DP
动态规划的基本原则是：先接近小问题，再逐步解决类似的大问题我们用表格来记录小问题，先完成一个亿点点的小目标：
我们来完成生命中第一个DP问题：
动态有点大，我裁成了4份：
我们完成了第一个DP问题。总结一下：表格的每一个格子代表了一个DP小问题的最优解。 在往下逐步填满小格子时， 我们不断的在重用已经解决的小问题的答案。或者说把新的问题分解为已经解决的小问题。
问题1： 如果又发现一个仙品，怎么办？
如果再来一个物品，我们只要给表格再加一行就好：
问题2：如果仙品的重量不是整数，怎么办？
需要重新设计表格，因为我们需要包含更多的小问题。
赞 (0)