LeetCode Note Java 00070：Climbing Stairs

爬樓梯經典題，一步可以走一或兩階，n 階的樓梯有幾種走法。

題目

Climbing Stairs Easy

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

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

我的解法

經典題，推算幾階之後會發現是費式數列的規則：第 n 階方法數 = (第 n - 1 階方法數) + (第 n - 2 階方法數)。

n=1 1=1
n=2 1+1=2
n=3 1+2=3
n=4 1+3+1=5
n=5 1+4+3=8
n=6 1+5+6+1=13 開始不好算
n=7 1+6+10+4=21 直接算錯

不過最難的地方就是要發現這規則，我自己是推算到n=6開始感到吃力，甚至可能算錯，所以這種找規律的題目最好在五組內就定下公式。

一維動態規劃：

n	1	2	3	4	5
方法數	1	2	3	5	8

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
          return n; // n <= 2 要另外處理
        }
        int[] array = new int[n];
        array[0] = 1;
        array[1] = 2;
        for (int i = 2; i < n; i++) {
          array[i] = array[i - 1] + array[i - 2];
        }
        return array[n - 1];
    }
}