基于Go和PHP语言实现爬楼梯算法的思路详解
爬楼梯（Climbing-Stairs）
题干：
假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定n是一个正整数。示例1： 输入：2 输出：2 解释：有两种方法可以爬到楼顶。 1.1阶+1阶 2.2阶示例2： 输入：3 输出：3 解释：有三种方法可以爬到楼顶。 1.1阶+1阶+1阶 2.1阶+2阶 3.2阶+1阶来源：力扣
这题爬楼梯算是算法题里面比较经典的。
解题思路
这题的解题思路主要有两种：
1.动态规划
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符合斐波那契数列规律，所以直接上代码咯！
Go实现
//斐波那契数列
//11235813....
funcclimbStairs2(nint)int{
//1阶台阶直接返回1
ifn==1{
return1
}
//2阶台阶直接返回2
ifn==2{
return2
}
current:=2
pre:=1
//当前台阶的走法是前两个台阶走法之和
fori:=3;i<=n;i++{
current=current+pre
pre=current-pre
}
returncurrent
}
PHP实现，一共两版实现，看自己喜欢哪种代码吧
functionclimbStairs($n){
//if($n==1)return1;
//$dp[1]=1;
//$dp[2]=2;
//for($i=3;$i<=$n;$i++){
//$dp[$i]=$dp[$i-1]+$dp[$i-2];
//}
//
//return$dp[$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];
}
总结
到此这篇关于基于Go和PHP语言实现爬楼梯算法的思路详解的文章就介绍到这了,更多相关GoPHP爬楼梯算法内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！