侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

经典算法题:爬楼梯 ,以斐波那契数列来解题代码案例

php  /  管理员 发布于 5年前   1637

网上这题的解题思路主要有两种:

  1. 动态规划 

  2. 斐波那契数列


因为我们用斐波那契数列来解,所以我主要描述方法2.


斐波那契数列 又称 兔子数列,

指得是:1、1、2、3、5、8、13、21、……,

在数学上它得递推公式是:

F(1)=1,

F(2)=1, 

F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)。


放到这个题目中我们可以发现:

二阶楼梯的走法有 2 种:

1 阶 + 1 阶 、 2 阶


三阶楼梯的走法有 3 种:

1 阶 + 1 阶、1 阶 + 2 阶、2 阶 + 1 阶


四阶楼梯的走法有 5 种:

1 阶 + 1 阶 + 1 阶 + 1 阶、1 阶 + 2 阶 + 1 阶、1 阶 + 1 阶 + 2 阶、2 阶 + 2 阶、2 阶 + 1 阶 + 1 阶

……


综上,

我们可以发现 n 阶楼梯有 m 种爬法,且 m 符合斐波那契数列规律.


php代码实现:(两种写法,有兴趣的可以自己研究)

1.
function climbStairs($n) {
     if($n<=2) return $n;
     $dp = [1=>1,2=>2];
     
     foreach(range(3,$n+1) as $v){
        //递归加法,这个爬楼梯就是斐波拉切算法求最后f(n-1)+f(n-2)的和
         $dp[$v] = $dp[$v-1]+$dp[$v-2]; 
     }
       return $dp[$n];
}

2.
function climbStairs($n) {
    if ($n <= 2) return $n;
    $dp = [1 => 1, 2 => 2];
    
    for ($i = 3; $i <= $n; $i++) {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    return $dp[$n];
}




  • 上一条:
    svn常用命令记录
    下一条:
    laravel-admin 添加Excel导出功能
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • 用Time Warden监控PHP中的代码处理时间(0个评论)
    • 在PHP中使用array_pop + yield实现读取超大型目录功能示例(0个评论)
    • Property Hooks RFC在PHP 8.4中越来越接近现实(0个评论)
    • 近期文章
    • 智能合约Solidity学习CryptoZombie二课:让你的僵尸猎食(0个评论)
    • 智能合约Solidity学习CryptoZombie第一课:生成一只你的僵尸(0个评论)
    • 在go中实现一个常用的先进先出的缓存淘汰算法示例代码(0个评论)
    • 在go+gin中使用"github.com/skip2/go-qrcode"实现url转二维码功能(0个评论)
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-11
    • 2017-12
    • 2018-01
    • 2018-02
    • 2018-03
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2020-07
    • 2020-09
    • 2021-02
    • 2021-03
    • 2021-04
    • 2021-05
    • 2021-06
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2021-12
    • 2022-01
    • 2022-02
    • 2022-05
    • 2022-06
    • 2022-07
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-08
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    • 2024-05
    • 2024-06
    • 2024-07
    • 2024-09
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客