经典算法题:爬楼梯 ,以斐波那契数列来解题代码案例
php  /  管理员 发布于 4年前   1570
网上这题的解题思路主要有两种:
动态规划
斐波那契数列
因为我们用斐波那契数列来解,所以我主要描述方法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]; }
123 在
Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..原梓番博客 在
在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..博主 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..1111 在
佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..路人 在
php中使用hyperf框架调用讯飞星火大模型实现国内版chatgpt功能示例中评论 教程很详细,如果加个前端chatgpt对话页面就完美了..Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号