经典算法题:爬楼梯 ,以斐波那契数列来解题代码案例
php  /  管理员 发布于 1年前   937
网上这题的解题思路主要有两种:
动态规划
斐波那契数列
因为我们用斐波那契数列来解,所以我主要描述方法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]; }
博主 在
hyperf框架常用命令-在centos7中退出命令及在docker容器中退出命令中评论 @路过的靓仔:cdn静态资源被墙,已修复..GGGGGGGGG 在
layui框架常用输入框介绍中评论 写的很好解决问题..路过的靓仔 在
hyperf框架常用命令-在centos7中退出命令及在docker容器中退出命令中评论 剩下好多 wait 状态的..激光豆芽 在
为什么你不能安逸?国内996为什么没有国外955香?中评论 国内现在无意义的内卷太多了..激光豆芽 在
阿里云香港服务器搭建自用vpn:Shadowsocks使用流程步骤中评论 厉害了..
Copyright·© 2019 侯体宗版权所有·
粤ICP备20027696号