动态规划

​ 动态规划一般来说和分治有点类似都是让他们去处理相同的子问题,但是在动态规划里面你会遇到更多的相同子问题。然后我们就会导致很多的重复计算,所以一般我们可以使用递归来完成一个动态规划要完成的任务,但是这样一般会重复计算很多东西,所以动态规划一般就增加了一些矩阵来存放上一次计算的结果。

​ 例如斐波那契数列,这个如果我们直接使用地柜计算的话,我们会很多重复计算。然后当我们要使用一个阵列计算的时候我们在每一次计算之前我们都需要进行一次判断看看我们目前的结果是不是已经被计算了,如果计算了就相当于查表直接获取答案,否则我们才开始计算。

状态:状态就是对于每一个字问题都可以使用一个数字 n 来描述这个子问题,如果状态相同就说明他们的答案相同。

​ 状态也可以有很多维度,例如排列组合就可以使用二维的,距离使用三维的,所谓的维度就是影响这个子问题的因素,也就是上面的那个 n 以及其他自定义的 j 等等!

状态转移方程:就是使用当前的状态来获取其他的状态。

​ 一般状态转移方程可以使用 top down 也可使用 bottom up 方法。

​ 给一个例子:现在有红 绿 蓝 三种颜色的油漆图一面墙,这面墙 红绿 和 绿蓝不能相邻问共有多少中涂色的方法。

​ 状态:定义长度为 n 的时候的涂色的方法数,然后出事值就是当 n 等于 1 的时候涂色的方法就是三种。但是这样我们发现很难写出状态方程,所以我们就再添加一个维度。第二个维度的意思就是颜色。

于是就可以得到这样的状态转移方程。看起来稍微有点复杂。而我们最后求结果就是

另外一个例子就是骨牌的问题,这个问题就是费时数列的问题,但是我们需要自己进行研究开始的几种情况。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 枚举

    ​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

    lwen
  • MyBatis笔记二:配置

    可以看到我们使用 <properties resource="db.properties"/> 引入了我们的数据据库的配置文件,然后这个标签有两个属性 : r...

    lwen
  • MyBatis笔记二:配置

    lwen
  • 你说的案发时间和Apple Watch讲的不一样!

    一起表面看来是行窃杀人的案件,其实却是死者亲属的亲手策划,而让真相水落石出的,竟是一块小小的智能手表。如今,健身追踪器和它们收集的数据已经成为了刑事调查的得力助...

    大数据文摘
  • 图解jdk1.8新特性(2)---Lambda

    SecondWorld
  • 查看依赖maven视图

    2.通过idea查看(在pom.xml->右键->Diagrams->Show Dependencies.)

    逍遥壮士
  • 钱塘一周说 | 大数据应用广泛 国家政策扶持力度或加大

    www.qtbigdata.com 新闻速报1 大数据应用广泛 国家政策扶持力度或加大 据之前经济参考报等媒体报道,包括大数据产业“十三五”规划在内的多...

    钱塘数据
  • 八个意想不到的数学事实

    总有一些东西听上去违背常理,可却是事实。数学就可以带给你这样的惊喜,今天我们就来为大家列举几个用数学就能解决的既简单又让人意外的小问题。

    Jean
  • 原创FlowPortal用户手写签名插件:Signature,需要另购手写板(及手写笔)

    近期人事部提出需求,要给所有的工人使用电脑请假申请,代替纸质的申请。因为不可能给每一位工人开设Windows或者应用系统账号,更不可能给每一个工人配置电脑,所以...

    崔文远TroyCui
  • 新一代大数据实时数据架构到底长啥样

    随着互联网的发展进入下半场,数据的时效性对企业的精细化运营越来越重要, 商场如战场,在每天产生的海量数据中,如何能实时有效的挖掘出有价值的信息, 对企业的决策运...

    zhisheng

扫码关注云+社区

领取腾讯云代金券