70-爬樓梯（Climbing Stairs）

題目描述

中文

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。
           

英文

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.
           

示例1

輸入： 2
	輸出： 2
	解釋： 有兩種方法可以爬到樓頂。
	1.  1 階 + 1 階
	2.  2 階
           

示例2

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.  1 階 + 1 階 + 1 階
2.  1 階 + 2 階
3.  2 階 + 1 階
           

題目分析

• 我們先來簡單分析：對于一個樓梯，我們一次隻能上一階或者兩階，是以這一步我們會有兩種選擇，如果我們選擇了一階，那麼下一步同樣會面臨這個問題。是以我們就會得到這樣一個公式：n階總次數 = n-1階總次數 + n-2階總次數，這樣一來用遞歸就可以很輕松的完成要求。

class Solution {
    public int climbStairs(int n) {
        if(n == 1)					//遞歸出口
            return 1;
        if(n == 2)					//遞歸出口
            return 2;
        else
            return climbStairs(n-1) + climbStairs(n-2);
    }
}
           

• 可是對于遞歸我們都很了解，他的效率是十分低下的，那麼能不能将他優化一下，使得效率有所提升呢？很明顯是有的。
• 對于普通遞歸，我們知道他效率低下的主要方面是因為大量資料的重複計算，這樣我們就可以用一個數組把算過的資料存起來，如果下次仍然需要用到，我們就直接查找，這樣效率就提高了很多。

class Solution {
    public int climbStairs(int n) {
        int flag[] = new int[n + 1];            //flag存儲計算過的台階數的解決方案
        return climb_Stairs(n,flag);
    }
    public int climb_Stairs(int n, int [] flag) {
        if(n == 1 || n == 0)
            return 1;
        if(n < 0)
            return 0;
        if(flag[n] > 0)
            return flag[n];
        else
            flag[n] = (climb_Stairs(n-1,flag) + climb_Stairs(n-2,flag));
        return flag[n];
    }
}
           

• 到了這裡，運作速度已經可以滿足LeetCode上的時間限制了，可是有沒有辦法更快的求出這個題的解呢？答案是有的，那就是使用動态規劃，對于動态規劃不了解的可以點選這裡，那麼用動态規劃怎麼解決這道題目呢？

  如果對動态規劃有所了解，那麼你一定清楚動态規劃的核心步驟是什麼。對，沒錯，就是找到規劃方程。那麼這道題的
   規劃方程到底是什麼呢。
             

階數	步數
1	1
2	2
3	2+1=3
4	3+2=5
5	5+3=8

• 到了這裡是不是已經很明了了呢？他是不是讓你想到了什麼東西？沒錯，就是斐波那契數列，現在，我們來看這道題的題解。

class Solution {
    public int climbStairs(int n) {
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        int a = 1,b = 2,c = 0,i = 2;
        while(i < n){
            c = a + b;
            a = b;
            b = c;
            i++;
        }
        return c;
    }
}
           

最後附上今天的python代碼

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        a = 1
        b = 2
        c = 0
        i = 2
        while i < n:
            c = a + b
            a = b
            b = c
            i += 1
        return c 
           

今天的題目就到此為止了，我們下次再見。