假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1 階 + 1 階
2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1 階 + 1 階 + 1 階
1 階 + 2 階
2 階 + 1 階

解

動(dòng)態(tài)規(guī)劃解決，從第n個(gè)點(diǎn)到第n+1個(gè)點(diǎn)時(shí)，可以在第n個(gè)點(diǎn)的基礎(chǔ)上向前一步，也可以在第n-1個(gè)點(diǎn)上向前2步，所以：
f(n+1) = f(n)+f(n-1)

public static int climbStairs(int n) {
        if(0==n)
            return 0;
        if(1==n)
            return 1;
        if(2==n)
            return 2;
        int res[] = new int[n+1];
        res[1] = 1;
        res[2] = 2;
        for(int i = 3;i<=n;i++) {
            res[i] = res[i-1]+res[i-2]; 
        }   
        return res[n];
    }