基于Go和PHP语言实现爬楼梯算法的思路详解

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《基于Go和PHP语言实现爬楼梯算法的思路详解》，聊聊算法、gophp、爬楼梯，希望可以帮助到正在努力赚钱的你。

爬楼梯（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 实现

// 斐波那契数列
// 1 1 2 3 5 8 13 ....
func climbStairs2(n int) int {
 // 1 阶台阶直接返回 1
 if n == 1 {
  return 1
 }
 // 2 阶台阶直接返回 2
 if n == 2 {
  return 2
 }
 current := 2
 pre := 1
 // 当前台阶的走法是前两个台阶走法之和
 for i := 3; i 

<p><strong>PHP 实现，一共两版实现，看自己喜欢哪种代码吧</strong></p>

<pre class="brush:php;">
function climbStairs($n) {
 // if($n==1) return 1;
 // $dp[1]=1;
 // $dp[2]=2;
 // for($i=3;$i 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语言实现爬楼梯算法的思路详解》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识，快来关注吧！