20190905：（leetcode習題）爬樓梯

爬樓梯

• 題目
• 大緻思路
• 代碼實作

題目

大緻思路

1. 這題我們先羅列一下結果，找規律即可。
2. n=1 1
3. n=2 2
4. n=3 3
5. n=4 5 1111 112 121 22 211
6. n=5 8 11111 1112 1121 1211 122 2111 212 221
7. 規律為，第n個結果為n-1的結果+n-2的結果，是以變為一道數學題。

代碼實作

class Solution {
    public int climbStairs(int n) {
    	//這個判斷必須加，否則索引出界，報錯：java.lang.ArrayIndexOutOfBoundsException
        if(n==1) 
            return 1;
        int[] res = new int[n+1];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i = 3;i<n+1;i++){
            res[i] = res[i-1]+res[i-2];
        }
        return res[n];
    }
}