亚洲一级黄色视频免费观看_国产亚洲精品综合在线网站_亚洲Av无码精品一区二区三区_特级无码一区二区三区毛片

主頁(yè) > 知識庫 > 基于Go和PHP語(yǔ)言實(shí)現爬樓梯算法的思路詳解

基于Go和PHP語(yǔ)言實(shí)現爬樓梯算法的思路詳解

熱門(mén)標簽:鐵路電話(huà)系統 網(wǎng)站排名優(yōu)化 百度競價(jià)排名 地方門(mén)戶(hù)網(wǎng)站 AI電銷(xiāo) Linux服務(wù)器 服務(wù)外包 呼叫中心市場(chǎng)需求

爬樓梯(Climbing-Stairs)

題干:

假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個(gè)臺階。你有多少種不同的方法可以爬到樓頂呢?注意:給定 n 是一個(gè)正整數。示例 1:  輸入: 2  輸出: 2  解釋?zhuān)?有兩種方法可以爬到樓頂。  1. 1 階 + 1 階  2. 2 階示例 2:  輸入: 3  輸出: 3  解釋?zhuān)?有三種方法可以爬到樓頂。  1. 1 階 + 1 階 + 1 階  2. 1 階 + 2 階  3. 2 階 + 1 階來(lái)源:力扣

這題爬樓梯算是算法題里面比較經(jīng)典的。

解題思路

這題的解題思路主要有兩種:

1.動(dòng)態(tài)規劃

2.斐波那契數列

動(dòng)態(tài)規劃算是一個(gè)比較重要的解題技巧與思路,后續我會(huì )寫(xiě)一系列需要用動(dòng)態(tài)規劃思路解題的文章,幫助大家更好的理解動(dòng)態(tài)規劃。

這題我們用斐波那契數列來(lái)解。

斐波那契數列又稱(chēng)兔子數列,指得是:1、1、2、3、5、8、13、21、……,在數學(xué)上它得遞推公式是:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)。

放到這個(gè)題目中我們可以發(fā)現:二階樓梯的走法有 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ā)現 n 階樓梯有 m 種爬法,且 m 符合斐波那契數列規律,所以直接上代碼咯!

Go 實(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
 // 當前臺階的走法是前兩個(gè)臺階走法之和
 for i := 3; i = n;i ++ {
  current = current + pre
  pre = current - pre
 }
 return current
}

PHP 實(shí)現,一共兩版實(shí)現,看自己喜歡哪種代碼吧

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){
  //遞歸加法,這個(gè)爬樓梯就是斐波拉切算法求最后f(n-1)+f(n-2)的和
  $dp[$v] = $dp[$v-1] + $dp[$v-2]; 
 }

 return $dp[$n];
}

總結

到此這篇關(guān)于基于Go和PHP語(yǔ)言實(shí)現爬樓梯算法的思路詳解的文章就介紹到這了,更多相關(guān)Go PHP 爬樓梯算法內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

您可能感興趣的文章:
  • 詳解PHP調用Go服務(wù)的正確方式
  • goto語(yǔ)法在PHP中的使用教程
  • ThinkPHP5 框架引入 Go AOP,PHP AOP編程項目詳解
  • golang、python、php、c++、c、java、Nodejs性能對比
  • Linux安裝PHP MongoDB驅動(dòng)
  • PHP中安裝使用mongodb數據庫
  • 詳解Go語(yǔ)言微服務(wù)開(kāi)發(fā)框架之Go chassis
  • 詳解Go與PHP的語(yǔ)法對比

標簽:銅川 蘭州 黃山 湖南 衡水 湘潭 崇左 仙桃

巨人網(wǎng)絡(luò )通訊聲明:本文標題《基于Go和PHP語(yǔ)言實(shí)現爬樓梯算法的思路詳解》,本文關(guān)鍵詞  ;如發(fā)現本文內容存在版權問(wèn)題,煩請提供相關(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內容系統采集于網(wǎng)絡(luò ),涉及言論、版權與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 收縮
    • 微信客服
    • 微信二維碼
    • 電話(huà)咨詢(xún)

    • 400-1100-266