Climbing Stairs

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

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

爬楼梯，一次只能走一格或两格，求有多少种不同走法可以走完n格楼梯。 如果楼梯只有1格，那只有一种走法 如果楼梯有2格，那可以走2次一格或1次两格，即两种走法 如果楼梯有3格，那可以3次1格，1次两格加2次一格，2次1格加1次两格，即三种走法

这就是一个斐波那契数列，n格的走法就是n－1格走法加n－2格走法的和. 注意初始化数组的长度，n格楼梯，需要n+1格长度（楼梯从1计数，数组从0计数）

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

public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    if (n == 0 || n == 1 || n == 2) {
        return n;
    }

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

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