动态规划(DP)

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

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

DP是个比较难的概念。

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


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

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

下面主角登场了——DP

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

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

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

动态有点大,我裁成了4份:

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

问题1:  如果又发现一个仙品,怎么办?

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

问题2:如果仙品的重量不是整数,怎么办?

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

(0)

相关推荐

  • 动态规划答疑篇

    ----------- 这篇文章就给你讲明白两个问题: 1.到底什么才叫「最优子结构」,和动态规划什么关系. 2.为什么动态规划遍历 dp 数组的方式五花八门,有的正着遍历,有的倒着遍历,有的斜着遍历 ...

  • 经典动态规划:0-1 背包问题

    前言 经过前面三篇动态规划文章的介绍,相信大家对动态规划.分治.贪心有了充分的理解,对动态规划的 3 个核心问题.其本质也有了了解. 纸上得来终觉浅,绝知此事要躬行. 那么今天开始我们来聊聊具体的那些 ...

  • 剑指 Offer 14- I. 剪绳子

    我服了.动态规划杀我. 可以说一说解决动态规划的思路(只做了两三道就总结了emmm) 1.识别动态规划问题 --重叠子问题:大问题可以分为一个个子问题.和分治策略分割的子问题不同(分治问题的子问题是相 ...

  • Python|动态规划问题--斐波那契数列

    斐波那契数列斐波那契数列其表达式如下: 递归算法通过公式我们不难看出,其第一项和第二项为1,当x>=3时,斐波那契数列的第x项就等于其前两项的和.所以我们可以得出代码如下:public stat ...

  • 五大基本算法之动态规划算法 DP dynamic programming | Echo Blog

    dynamic programming 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法. 20世纪50年代初美 ...

  • P是AC上的动点,求BP DP的最小值,两个动点是将军饮马类型吗

    P是AC上的动点,求BP DP的最小值,两个动点是将军饮马类型吗

  • 基于动态规划的多站雷达协同探测信号级融合算法

    0 引言 随着战争的不断升级和军事科学技术的飞速发展,快速发展的隐身技术和不断出现的低空高速超高速目标.日新月异的电子侦察和雷达干扰技术等,对现代雷达工作构成了巨大的威胁[1].近几年,我国军事现代化 ...

  • DisplayPort 2.0 标准应用再次推迟;DP究竟怎么了?

    DisplayPort 2.0 视频传输标准于 2019 年发布初稿(DP放大招,DP2.0发布并兼容Thunderbolt3),此前计划于 2020 年年末发布首款产品,但目前还没有一款显示设备搭载 ...

  • 科普|Display Port DP 历史版本对比

    Display Port 是由VESA发布的显示接口规范, 基于数据包的可扩展视频音频传输协议 (DisplayPort is a packet-based, extensible protocol ...

  • Type-C科普之DP over USB-C

    最近几年,USB3.1/3.2/4标准.雷电 Thunderbolt 3.4.外置显卡.DP Altmode等一系列与Type-C紧密相关的词汇接踵而来,今天我们Type-C科普之DP over US ...

  • DP的目标是干掉HDMI

    DP和HDMI这对老冤家宿怨已久,一直誓言干掉对方,但是江湖仍是这个江湖,但他们的境遇已经到了另外一个境界,引用范李分手时候的经典名句,我们不再是我们,我们还是我们,USB C接口已经开始将开火目标瞄 ...

  • Python | 动态规划解决“返回第n个丑数”

    问题描述给你一个整数 n ,请你找出并返回第 n 个 丑数 .丑数 就是只包含质因数 2.3 和/或 5 的正整数.示例 1:输入:n = 10输出:12解释:[1, 2, 3, 4, 5, 6, 8 ...

  • 修模常用软件:DP、模方、SVS模型修复教程汇总

    原创 GIS前沿 GIS前沿 昨天 随着"实景三维中国建设"步伐的加快,倾斜市场的需求日益渐增,倾斜数据处理后的模型修复一直是我们比较关注的问题.在后台一直有不少伙伴询问关于模型修 ...