首页 > 其他分享 >什么是动态规划?

什么是动态规划?

时间:2022-08-28 17:47:03浏览次数:47  
标签:斐波 什么 问题 最优 动态 规划 那契

  • 什么是动态规划?

今天简单说一下动态规划的定义以及简单示例。动态规划,是一种将原问题分解成简单的子问题来解决复杂问题的思想。

其中,动态规划还具有最优子结构性质和子问题重叠性质。

最优子结构:动态规划将原问题分解成各种简单的子问题时,各个子问题的最优解综合起来就是原问题的最优解,即局部最优解能够决定全局最优解。

子问题重叠:在计算一个子问题的最优解之后,记住这个子问题,接下来还可能遇到相同问题,为提高效率,可以直接拿来之前得到的结果,这是因为当使用递归自顶向下的时候,每次产生的子问题不总是新问题,而是之前被重复计算的问题。

  • 斐波那契数列

接下来简单利用斐波那契数列来介绍一下动态规划:

斐波那契数列:0,1,1,2,3,5,8,13,21,34,55,89、、、、、、规律是从第三项开始,每一项都等于前两项之和,F(n)=F(n-1)+F(n-2),(n>=3)

问题简单描述:

给一个整型数值n,输出斐波那契数列中对应的第n项数值

在不了解动态规划地情况下,我们一般都是利用普通递归来解决

1 public int fabocci(int n){
2     if(n<1)
3         return 0;
4     else if(n==1)
5         return 1;
6     else if(n==2)
7         return 1;
8     return fabocci(n-1)+fabocci(n-2);
9 }

 

显然每次调用fabocci函数时,因为第三项之后都是前两项之和,所以会出现大量的重复计算,且时间复杂度为O(2^n)

基于相邻两项之和可以推出下一项,于是可以采用自底向上的方法:

 1 public int fabocci(int n){
 2     if(n<1)
 3         return 0;
 4     else if(n==1)
 5         return 1;
 6     else if(n==2)
 7         return 1;
 8 //temp1,temp2既是相邻两项的值,也是为了记录迭代出来的结果,方便下一次计算使用
 9     int temp1=1;
10     int temp2=1;
11     int temp=0;
12     for(int i=3;i<=n;i++){
13         temp=temp1+temp2;
14         temp1=temp2;
15         temp2=temp;
16     }
17     return temp;
18 }

以上仅以学习记录,如有问题,请及时指正,我们共同进步,谢谢!

 

标签:斐波,什么,问题,最优,动态,规划,那契
From: https://www.cnblogs.com/TiAmo-bai/p/16633206.html

相关文章

  • 为什么Go源码中有些函数没有函数体?
    在Go源码中,有时候我们点开查看,会发现这样的东西:这些是没有函数体的,这是为什么呢?这些是runtime的,也就是实现不是用Go写的,这一类方法,有些用汇编写的,有一些用C写的,可......
  • 【动植物研究动态】20220815文献解读
    目录HorticRes|武汉大学李家儒:盾叶薯蓣高质量基因组解析与薯蓣皂苷生物合成进化TheCropJournal|华南农业大学肖德琴:一种新的水稻穗多发育期自动识别算法TheCropJo......
  • 闭包有什么作用
    (1)什么是闭包:闭包是指有权访问另外一个函数作用域中的变量的函数。闭包就是函数的局部变量集合,只是这些局部变量在函数返回后会继续存在。闭包就是就是函数的“堆栈”在......
  • 【动植物研究动态】20220828文献解读
    目录ScienceBulletin|中国农科院作科所徐建龙&邱丽娟:大豆种质资源组学数据库SoyFGBv2.0搭建SCLS|种康、贾继增等:中国小麦基因组学和性状改良研究综述TheCropJourna......
  • Echarts与ajax数据的动态交互
    初学Echarts,Echarts的官网示例中配置项的数据需要用到js数组来传递数据,所以当我们从后端查询到数据后,往往需要通过ajax来进行数据交互。这是官方示例的配置项。<script......
  • 关于vue的css样式对js动态添加的dom节点不生效问题的解决方法
    一、问题描述开发的时候免不了有时候需要向某个节点appendchild,添加子节点,但是如果是在vue中,就会发现通过操作dom的appendchild方式添加节点会出现样式对这些新增的节点......
  • 十万个为什么
    get/post区别resltfull风格主要是做了对浏览器请求的过滤。做了对地址栏数据的参数替换为""https://www.cnblogs.com/murmansk/p/11469752.html错误码100到5xxhtt......
  • 一文搞懂什么是缓存穿透、缓存击穿、缓存雪崩!
    什么是缓存穿透、缓存击穿、缓存雪崩?面试的时候关于Redis问得最多的问题,可能就是:请你简单说说什么是缓存穿透、缓存击穿、缓存雪崩?由于这三种说法的名字很相近,很多同学经......
  • 什么是 MyBatis?
    1.MyBatis是一款优秀的持久层框架2.它支持自定义SQL、存储过程以及高级映射。MyBatis免除了几乎所有的JDBC代码以及设置参数和获取结果集的工作。MyBatis可以通过简......
  • 为什么需要 Cookie 和 Session,他们有什么关联?
    为什么需要Cookie和Session说起来为什么需要Cookie,这就需要从浏览器开始说起,我们都知道浏览器是没有状态的(HTTP协议无状态),这意味着浏览器并不知道是张三还是李四......