欢迎您的到来!     
注册用户 [请登录]      新用户 [免费注册]     
网站首页 电子教程 视频教程 在线题库 毕业设计 疑难解答 IT技术文章
疑难问题分类
毕业设计
小程序毕设   Java毕设   PHP毕设  
前端界面
HTML   CSS   Bootstrap  
前端JS
JavaScript   jQuery   Vue.js   React.JS   AngularJS  
后端开发
ASP   PHP   JSP   NET   Python  
数据库
SQL   MySQL  
移动开发
WEBAPP   微信小程序  
其他技术
其他计算机技术  
 文章详情:动态规划入门到熟悉,看不懂来打我啊

算。那很容易想到如果我们把计算的结果全都保存下来,按照一定的顺序推出n项,就可以提升效率


 


解法2:


def f1(n):

    if n==1 or n==2:

        return 1

    l=[0]*n                #保存结果

    l[0],l[1]=1,1            #赋初值

    for i in range(2,n):

        l[i]=l[i-1]+l[i-2]     #直接利用之前结果

    return l[-1]

可以看出,时间o(n),空间o(n)。


继续思考,既然只求第n项,而斐波那契又严格依赖前两项,那我们何必记录那么多值浪费空间呢?只记录前两项就可以了。


 


解法3:


def f2(n):

    a,b=1,1

    for i in range(n-1):

        a,b=b,a+b

    return a

补充:


pat、蓝桥杯等比赛原题:求的n很大,F(N)模一个数。应每个结果都对这个数取模,否则:第一,计算量巨大,浪费时间;第二,数据太大,爆内存,

对于有多组输入并且所求结果类似的题,可以先求出所有结果存起来,然后直接接受每一个元素,在表中查找相应答案

此题有快速幂算法,但是碍于篇幅和同学们水平有限,不再叙述,可以自行学习。

 


例2:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。


 


依旧是找递推关系:


1)跳一阶,就一种方法


2)跳两阶,它可以一次跳两个,也可以一个一个跳,所以有两种


3)三个及三个以上,假设为n阶,青蛙可以是跳一阶来到这里,或者跳两阶来到这里,只有这两种方法。


它跳一阶来到这里,说明它上一次跳到n-1阶,


同理,它也可以从n-2跳过来

————————————————

版权声明:本文为CSDN博主「一只大白兔兔兔兔兔」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/hebtu666/article/details/100585136


上一篇: 暂无 下一篇: 面试官:关于Java性能优化,你有什么技巧


第一步:学习免费电子文档;   第二步:在线测试考试;   第三步:选择收费视频学习;   第四步:学习技术文章和疑难解答.
友情链接: 微信小程序中文网  |   毕业设计网  |   小程序教学网  |   计算机教程网  |   小白教程网  |   网页网站毕业设计网
浙ICP备18013434号-3 Copyright ©2020 小白教程网 www.2d5.net (QQ交流群:147415688). Technical support/技术支持:杭州摇亿网络科技