maxcian der TechBlog

 數學歸納法，從n = 1開始列排列組合找pattern：

1. n=1, 1
2. n=2, 2
3. n=3, 3
4. n=4, 5
5. n=5, 8
6. n=6, 13

就會發現是所謂的Fibonacci number

那做法就變得直覺了，先開一個足夠大小的array，然後初始n=1與n=2的值，因為n≧3之後：

 

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

 

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0) return 0;
        else if (n == 1) return 1;
        int container[n];
        container[0] = 1;
        container[1] = 2;
        for (int i = 2; i < n; ++i)
            container[i] = container[i-1] + container[i-2];
        return container[n-1];
    }
};