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

C#代碼

public class Solution {

    //遞推公式確定：爬上第n階臺階有兩種方法：從第n-1階爬一個臺階到達；從第n-2階爬2個臺階到達。則：dp[n]=dp[n-1]+dp[n-2]
    //邊界條件：dp[0]=1;dp[1]=1;
    public int ClimbStairs(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;

        for(int i=2;i<n+1;i++)
            dp[i]=dp[i-1]+dp[i-2];
        
        return dp[n];
    }
}