【算法入門08】青蛙跳台階

核心考點：場景轉化模型，模型提取解法，簡單dp，fib

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求青蛙跳上一個n級的台階共有多少種跳法（先後次序不同算不同的結果）。

解析：

對于這道題目，我們若是使用正向思維去思考，那這道題會變得非常困難，這時我們可以考慮使用逆向思維。

既然青蛙最終會到達第n級台階，那青蛙必定是從第n-1級台階或是第n-2級台階跳到第n級台階的。

也就是說青蛙跳到第n級台階的總跳法數，等于青蛙跳到第n-1級台階的總跳法數和青蛙跳到第n-2級台階的總跳法數之和，即。

當然，我們不能讓這個公式一直往前推，總得給它一個盡頭，我們很容易得到青蛙跳到第0級台階的總跳法數，和青蛙跳到第1級台階的總跳法數：

• ，青蛙跳到第0級台階的跳法隻有一種，那就是不跳。
• ，青蛙跳到第1級台階的跳法也隻有一種，那就是從第0級台階直接跳到第1級台階。

這時代碼也就出來了，我們可以使用遞歸來解決該問題：

//遞歸
class Solution {
public:
  int jumpFloor(int number) {
    if (number == 0 || number == 1) //f(0)=1, f(1)=1
      return 1;
    return jumpFloor(number - 1) + jumpFloor(number - 2); //f(n)=f(n-1)+f(n-2)
  }
};      

//動規
class Solution {
public:
  int jumpFloor(int number) {
    if (number == 0 || number == 1) //f(0)=1, f(1)=1
      return 1;
    int first = 1; //f(0)=1
    int second = 1; //f(1)=1
    int third = 0;
    while (number > 1) //進行number-1次計算
    {
      //f(n)=f(n-1)+f(n-2)
      third = first + second;
      first = second;
      second = third;
      number--;
    }
    return third;
  }
};