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?
Note: Given n will be a positive integer.
爬楼梯，非常经典的一道题。题意是每次你可以迈一个或两个台阶，那么爬到第n个台阶一共有多少种方法？
由题意可知有两种方法可以爬到第n个台阶，即从第n-1个台阶迈一阶或从第n-2个台阶迈两阶，如果我们用f(i)表示爬到第i阶的方法数，则f(n) = f(n-1) + f(n-2)。对于第1阶和第2阶，很容易知道f(1) = 1、f(2) = 2，我们把f(n)换成数组来表达，就可以解决这道题了。注意先判断n的值是否小于等于1，否则初始化数组dp[2]的值时会越界。
public int climbStairs(int n) {
if (n < 0) {
return -1;
}
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}