• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

DP问题详解 之 动态规划的优点

主编主编 NOIP信息学奥赛 2017-11-11 2,269 0

我们为什么需要使用动态规划呢?请先继续欣赏这个故事:

国王得知他的两个手下使用了和他相同的方法去解决交代给他们的问题后,不但没有认为他的两个大臣在偷懒,反而很高兴,因为他知道,他的大臣必然会找更多的人一起解决这个问题,而更多的人会找更更多的人,这样他这个聪明的方法就会在不经意间流传开来,而全国人民都会知道这个聪明的方法是他们伟大的国王想出来的,你说国王能不高兴吗?

但是国王也有一些担忧,因为他实在不知道这个“工程”要动用到多少人来完成,如果帮助他解决这个问题的人太多的话那么就太劳民伤财了。“会不会影响到今年的收成呢?”国王在心里想着这个问题,于是他请来了整个国家里唯一的两个数学天才,一个叫做小天,另一个叫做小才。

国王问小天:“小天啊,我发觉这个问题有点严重,我知道其实这可以简单的看成一个组合问题,也就是从十个金矿中选取若干个金矿进行开采,看看哪种组合得到的金子最多,也许用组合方法会更好一些。你能告诉我一共有多少种组合情况吗?”

“国王陛下,如果用组合方法的话一共要考虑2的10次方种情况,也就是1024种情况。”小天思考了一会回答到。

“嗯……,如果每一种情况我交给一个人去计算能得到的金子数的话,那我也要1024个人,其实还是挺多的。”国王好像再次感觉到了自己的方法是正确的。

国王心理期待着小才能够给它一个更好的答案,问到:“小才啊,那么你能告诉我用我的那个方法总共需要多少人吗?其实,我也计算过,好像需要的人数是1+2+4+8+16+32+64+……,毕竟每一个人的确都需要找另外两个人来帮助他们……”

不辜负国王的期待,小才微笑着说到:“亲爱的国王陛下,其实我们并不需要那么多人,因为有很多问题其实是相同的,而我们只需要为每一个不同的问题使用一个人力便可。”

国王高兴的问到:“此话如何讲?”

“打个比方,如果有一个人需要知道1000个人和3个金矿可以开采出多少金子,同时另一个人也需要知道1000个人和3个金矿可以开采出多少金子的话,那么他们可以去询问相同的一个人,而不用各自找不同的人浪费人力了。”

国王思考着说到:“嗯,很有道理,如果问题是一样的话那么就不需要去询问两个不同的人了,也就是说一个不同的问题仅需要一个人力,那么一共有多少个不同的问题呢?”

“因为每个问题的人数可以从0取到10000,而金矿数可以从0取到10,所以最多大约有10000 * 10 等于100000个不同的问题。” 小才一边算着一边回答。

“什么?十万个问题?十万个人力?”国王有点失望。

“请国王放心,事实上我们需要的人力远远小于这个数的,因为不是每一个问题都会遇到,也许我们仅需要一、两百个人力就可以解决这个问题了,这主要和各个金矿所需要的人数有关。” 小才立刻回答到。

故事的最后,自然是国王再一次向他的臣民们证明了他是这个国家里最聪明的人,现在我们通过故事的第二部分来考虑动态规划的另外两个思考点。DP问题详解 之 动态规划的优点-少儿编程教育网

思考动态规划的第五点—-做备忘录:

正如上面所说的一样,当我们遇到相同的问题时,我们可以问同一个人。讲的通俗一点就是,我们可以把问题的解放在一个变量中,如果再次遇到这个问题就直接从变量中获得答案,因此每一个问题仅会计算一遍,如果不做备忘的话,动态规划就没有任何优势可言了。

思考动态规划的第六点—-时间分析:

正如上面所说,如果我们用穷举的方法,至少需要2^n个常数时间,因为总共有2^n种情况需要考虑,如果在背包问题中,包的容量为1000,物品数为100,那么需要考虑2^100种情况,这个数大约为10的30次方。

而如果用动态规划,最多大概只有1000*100 = 100000个不同的问题,这和10的30次方比起来优势是很明显的。而实际情况并不会出现那么多不同的问题,比如在金矿模型中,如果所有的金矿所需人口都是1000个人,那么问题总数大约只有100个。

非正式地,我们可以很容易得到动态规划所需时间,如果共有questionCount个相同的子问题,而每一个问题需要面对chooseCount种选择时,我们所需时间就为questionCount * chooseCount个常数。在金矿模型中,子问题最多有大概people * n 个(其中people是用于开采金矿的总人数,n是金矿的总数),因此questionCount = people * n,而就像国王需要考虑是采用左部下的结果还是采用右部下的结果一样,每个问题面对两个选择,因此chooseCount = 2,所以程序运行时间为 T = O(questionCount * chooseCount) =O(people * n),别忘了实际上需要的时间小于这个值,根据所遇到的具体情况有所不同。

这就是动态规划的魔力,它减少了大量的计算,因此我们需要动态规划!

 

喜欢 (0)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

DP问题详解 之 初识动态规划

下一篇

震惊!原来这些名人都是编程大神!潘玮柏、许嵩、李显龙...

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • 少儿编程教育神器,树莓派4首次提供PC级性能和可编程性
    2019-07-03

    少儿编程教育神器,树莓派4首次提供PC级性能和可编程性

  • 为什么说少儿编程教育能极大提高孩子综合素质?

    为什么说少儿编程教育能极大提高孩子综合素质?

    2018-04-10
  • JavaScript少儿编程教程-第11课-字符串的大小写转换

    JavaScript少儿编程教程-第11课-字符串的大小写转换

    2018-01-26
  • 爸爸教我学Python编程-第15课-type()和类型转换

    爸爸教我学Python编程-第15课-type()和类型转换

    2018-04-14
  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

    2018-11-14

热门文章

    暂无文章

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号