LeetCode0070-爬樓梯

題目：

假設你正在爬樓梯。需要 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 階
           

代碼：

/**
 * 0070-爬樓梯
 * 假設你正在爬樓梯。需要 n 階你才能到達樓頂。
 * <p>
 * 每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
 * <p>
 * 注意：給定 n 是一個正整數。
 * <p>
 * 示例 1：
 * <p>
 * 輸入： 2
 * 輸出： 2
 * 解釋： 有兩種方法可以爬到樓頂。
 * 1.  1 階 + 1 階
 * 2.  2 階
 * <p>
 * 示例 2：
 * <p>
 * 輸入： 3
 * 輸出： 3
 * 解釋： 有三種方法可以爬到樓頂。
 * 1.  1 階 + 1 階 + 1 階
 * 2.  1 階 + 2 階
 * 3.  2 階 + 1 階
 * <p>
 * <p>
 * 分析：
 * 使用 f(x) 表示爬到第 x 級台階的方案數，考慮到最後一步可能跨越一級台階，也可能跨越倆級台階，是以：
 * f(x) = f(x-1) + f(x-2)
 * 其中 f(0) = 1， f(1）= 1
 * <p>
 * 分析：
 * 使用 f(x) 表示爬到第 x 級台階的方案數，考慮到最後一步可能跨越一級台階，也可能跨越倆級台階，是以：
 * f(x) = f(x-1) + f(x-2)
 * 其中 f(0) = 1， f(1）= 1
 */

/**
 * 分析：
 * 使用 f(x) 表示爬到第 x 級台階的方案數，考慮到最後一步可能跨越一級台階，也可能跨越倆級台階，是以：
 * f(x) = f(x-1) + f(x-2)
 * 其中 f(0) = 1， f(1）= 1
 */

/**
 * 遞歸實作，便于了解，LeetCode不能通過，超出時間限制
 */
class Solution01 {
    public int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

/**
 * 使用數組進行優化
 */
class Solution02 {
    public int climbStairs(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;
        for (int i = 2; i <= n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n];
    }
}

/**
 * 三個變量進行存儲，減少空間消耗
 */
class Solution03 {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}

/**
 * 測試
 */
public class Study0070 {
    public static void main(String[] args) {
        System.out.println(new Solution03().climbStairs(3));
    }
}

           

結果: