一個(gè)Ｎ階的樓梯，每次能１或著２階，問走n階的樓梯有多少種走法?

分析可知在走第ｎ階的時(shí)候，是與第n-1階和n-2階有關(guān)系的。用戶走到第ｎ階的方法應(yīng)該是用戶走到第n-1 n-2階的和。使用數(shù)學(xué)表達(dá)式應(yīng)該 如下：

當(dāng)n=1 或者n=2 時(shí)，f(n) = 1,所以我們可以考慮使用遞歸來實(shí)現(xiàn)

  　func ClimbStarisRecursion(n int) int{
          if n == 1 || n == 0{
              return 1
          }
          
          return ClimbStarisRecursion(n-2) + ClimbStarisRecursion(n-1)
     }

     func main(){
          step := 20
         fmt.Println(ClimbStarisRecursion(20))
     }

一般遞歸問題可以轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃問題來處理，相比于遞歸算法伴隨這會(huì)伴隨著較多的出棧入棧操作消耗，我們使用動(dòng)態(tài)規(guī)劃算法性能會(huì)優(yōu)于遞歸算法，下面我們給出動(dòng)態(tài)規(guī)劃的版本

    func ClimbStarisDP(n int) int{
         pre := 1
         now := 1
         var tmp int
         for i := 2;i <= n;i++{
             tmp = now
             now = pre + now
             pre = tmp
        }   
        return now
    }

算法問題的計(jì)算過程中，最重要的抽象出問題中的數(shù)學(xué)模型，然后根據(jù)數(shù)學(xué)模型找到合適的計(jì)算方法(遞歸，動(dòng)態(tài)規(guī)劃，貪婪算法)進(jìn)行代入求解是否能夠得到需要的問題。