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

斐波那契数列斐波那契数列其表达式如下:

递归算法通过公式我们不难看出,其第一项和第二项为1,当x>=3时,斐波那契数列的第x项就等于其前两项的和。所以我们可以得出代码如下:public static Integer fib(int n){if (n==1 || n==2){return 1;}return fib(n-2)+fib(n-1);}递归算法是自上而下的算法,要得出后面的值就得知道前两项的值,这样会产生大量重复计算,比如要求第七项的值,就需要知道第六项和第五项的值,要求第六项的值,就需要第五项和第四项的值,光这里就求了两次第五项的值,所以这种算法的效率不是很高。动态规划算法在使用递归时,我们看到了递归的不足,因为其存在大量重复函数的调用,效率很低。可以试试动态规划,通过保存前两项的值来求解第x项的值。其代码如下:public static Integer dp(int n){int[] dp = new int[n+1];dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}这里通过牺牲内存来保存每一项的值,就不需要重复计算而达到提高效率。到这里已然发现动态规划的简单原理:问题的最优解可以通过其子问题的最优解得到。若子问题有比较多的重复,则可以采用自底向上来计算。实习编辑:欧洋责编 :刘玉江能力越强,责任越大。实事求是,严谨细致。(where2go团队)微信号:算法与编程之美

(0)

相关推荐

  • PHP递归与迭代

    在 PHP 中,我们经常会遇到这样的情况:在面临一个庞大的问题时,需要把这个庞大的问题拆分成各个细小的单元,解决了每个细小单元的问题,这个庞大的问题便迎刃而解了.递归与迭代就是这种思想的体现. PHP ...

  • 动态规划详解

    这篇文章是我们号半年前一篇 200 多赞赏的成名之作 动态规划详解 的进阶版.由于账号迁移的原因,旧文无法被搜索到,所以我润色了本文,并添加了更多干货内容,希望本文成为解决动态规划的一部「指导方针」. ...

  • Python 编程别再用递归了

    递归函数使用起来非常酷,简洁优雅,可以用来炫耀编程技巧.但是,在大多数情况下,递归函数具有非常高的时间和空间复杂性,我们应该避免使用它.更好的解决方案之一是在可能的情况下使用动态规划,对于能够分解为子 ...

  • Python如何实现斐波那契数列?

    公众号新增加了一个栏目,就是每天给大家解答一道Python常见的面试题,反正每天不贪多,一天一题,正好合适,只希望这个面试栏目,给那些正在准备面试的同学,提供一点点帮助! 小猿会从最基础的面试题开始, ...

  • Python|递归函数之斐波那契数列

    上一期小编主要针对def函数的运用进行了简单的讲解,本期将会深入探讨def函数的另一种特别有用的函数(递归函数),其定义:如果一个函数在内部调自身,这个函数就是递归函数,递归函数的优点在于其定义简单, ...

  • 波浪理论:5、斐波那契数列与波浪变盘周期关系

    一.斐波那契数列 斐波那契数列指的是这样一个数列:0,1,1,2,3,5,8,13,21,34,55,89,144--这个数列从第三项开始,每一项都等于前两项之和. 很有趣的是:这样一个完全是自然数的 ...

  • 【通达信福利指标】斐波那契数列-副图选股指标公式

    【通达信福利指标】斐波那契数列-副图选股指标公式

  • 高中数学数列中的——斐波那契数列问题总结...

    高中数学数列中的--斐波那契数列问题总结(俗称兔子数列) (一)以斐波那契数列的概念 (二)以斐波那契数列的性质 (三)以斐波那契数列的模型 (四)以斐波那契数列的模型

  • 动态八卦中隐藏着神奇的斐波那契数列 是揭示宇宙变化的基本定律

    古人通过仰观俯察,近取诸身远取诸物,发明八卦,目的是模拟宇宙自然的变化规律,归纳解释万事万物现象.易是变化,周易就是研究变化的学问. 一分为二,阴阳变化是传统八卦理论的根本.所以说:易有太极,是生两仪 ...

  • 斐波那契数列与空中加油

    所谓空中加油形态,就是一只股票遭遇主力扫货,出现了连续跳空涨停之后,主力为了清洗浮筹,采取了凶狠洗盘动作,洗盘之后股票继续飞涨. 空中加油买入信号: 1.经过拉升后,进入良性"空中加油&qu ...

  • 技术分析最高境界:斐波纳契数列时间周期

    首先,来认识一下斐波纳契数列: 1-1-2-3-5-8-13-21-34-55-89-144-233-377- 宇宙运行规律 这个数列举世闻名,暗藏着宇宙运行的规律,甚至小到我们的细胞分裂.心理活动都 ...

  • 用数学来观察万物关联的法则,奇妙的斐波那契数列与螺旋线

    孩子们在探索世界的时候,从来不羞于一口气把关于风.水.云.山的问题问个遍.他们还很"无知",提出的问题比较笼统.慢慢地,他们开始体悟到生命的规律,尽管不了解其中的逻辑与原因,但还是 ...