经典算法题:爬楼梯 ,以斐波那契数列来解题代码案例
管理员 发布于 3年前 665
动态规划
斐波那契数列
网上这题的解题思路主要有两种：
因为我们用斐波那契数列来解，所以我主要描述方法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];
}请勿发布不友善或者负能量的内容。与人为善，比聪明更重要！
该博客于2020-12-7日，后端基于go语言的beego框架开发
前端页面使用Bootstrap可视化布局系统自动生成
是我仿的原来我的TP5框架写的博客，比较粗糙，底下是入口
侯体宗的博客
文章标签
- test 三种扣减库存方案 Hyperf2.1启动报错端口占用 上外网神器Ghelper 上外网神器集装箱 laravel中HMVC模式 Hyperf框架验证器 Hyperf自定义函数编写 Hyperf对象转成数组 PHP2021面试题集 centos7系统上挂载 Hyperf框架 秒杀系统的设计 Laravel Octane PHP数组底层实现原理 php7垃圾回收机制 Laravel中类型转换 mysql事务特征及隔离级别 Linux-awk命令 mysql编码 JWT源码实现 Laravel内核分析 Laravel中的用法 centos7+go环境+beego框架 go+beego框架开发博客 go+beego开发博客首页 go+beego自定义公共函数 beego注册_登录_查询 beego控制器创建 Beego框架安装 go语言环境安装 laravel+Elasticsearc laravel运行原理 windows7搭建Vuejs环境 Laravel分块 laravel去重(distinct() laravel集合 laravel+mysql读写分离 laravel5+复杂原生sql laravel+MissMyCat/al lnmp sessio laravel自定义数组分页 laravel中.env配置 laravel8队列发邮件 码云仓库常用操作 laravel8配置163SMTP laravel8配置全局函数 laravel/jetstream之认证 laravel/jetstream
友情链接
