溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了基于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 實現
// 斐波那契數列
// 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 <= n;i ++ {
current = current + pre
pre = current - pre
}
return current
}PHP 實現，一共兩版實現，看自己喜歡哪種代碼吧
function climbStairs($n) {
// if($n==1) return 1;
// $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語言如何實現爬樓梯算法的內容，如果你們有學習到知識或者技能，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
