爬樓梯（Climbing-Stairs）
題干：
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個正整數(shù)。示例 1： 輸入： 2 輸出： 2 解釋： 有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階示例 2： 輸入： 3 輸出： 3 解釋： 有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階來源：力扣
這題爬樓梯算是算法題里面比較經(jīng)典的。
解題思路
這題的解題思路主要有兩種：
1.動態(tài)規(guī)劃
2.斐波那契數(shù)列
動態(tài)規(guī)劃算是一個比較重要的解題技巧與思路，后續(xù)我會寫一系列需要用動態(tài)規(guī)劃思路解題的文章，幫助大家更好的理解動態(tài)規(guī)劃。
這題我們用斐波那契數(shù)列來解。
斐波那契數(shù)列又稱兔子數(shù)列，指得是：1、1、2、3、5、8、13、21、……，在數(shù)學(xué)上它得遞推公式是：F(1)=1，F(xiàn)(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。
放到這個題目中我們可以發(fā)現(xià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 階……
綜上，我們可以發(fā)現(xiàn) n 階樓梯有 m 種爬法，且 m 符合斐波那契數(shù)列規(guī)律，所以直接上代碼咯！
Go 實(shí)現(xiàn)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 斐波那契數(shù)列// 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 // 當(dāng)前臺階的走法是前兩個臺階走法之和 for i := 3; i <= n;i ++ { current = current + pre pre = current - pre } return current} |
PHP 實(shí)現(xiàn)，一共兩版實(shí)現(xiàn)，看自己喜歡哪種代碼吧
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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];} |
總結(jié)
到此這篇關(guān)于基于Go和PHP語言實(shí)現(xiàn)爬樓梯算法的思路詳解的文章就介紹到這了,更多相關(guān)Go PHP 爬樓梯算法內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：http://hxd.best/2020/05/17/Go和PHP-實(shí)現(xiàn)爬樓梯算法/
