【leetcode刷題】T159-爬樓梯

木又連續日更第19天（19/138）

木又的第159篇leetcode解題報告

動态規劃

類型第2篇解題報告

leetcode第70題：爬樓梯

https://leetcode-cn.com/problems/climbing-stairs/

【題目】

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

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

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

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

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

複制

【思路】

這道題，是典型的斐波那契數列題目，同類型的還包括：青蛙跳台階，砌方塊。

f(n) = f(n-1) + f(n-2)

當然，上式可以作為動态規劃遞推公式，不過，這道題不用這麼麻煩，哈哈哈。

【代碼】

python版本

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 斐波那契數列 f(n) = f(n-1) + f(n-2)
        if n < 3:
            return n
        a, b = 1, 1
        for i in range(1, n):
            a, b = b, a+b
        return b
           

複制

C++版本

class Solution {
public:
    int climbStairs(int n) {
        // 斐波那契數列 f(n) = f(n-1) + f(n-2)
        if(n < 3)
            return n;

        int a = 1, b = 1;
        int tmp = 0;
        for(int i=1; i<n; i++){
            tmp = a;
            a = b;
            b = tmp + b;
        }
        return b;
    }
};
           

複制