算法-爬楼梯

如果爬楼梯需要 n 阶你才能到达楼顶。（ n 是一个正整数）
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
例 1：n=2
解释： 有两种方法可以爬到楼顶。
第一种: 1 阶 + 1 阶
第二种： 2 阶

例 2：n=3
解释： 有三种方法可以爬到楼顶。
第一种：1 阶 + 1 阶 + 1 阶
第二种：1 阶 + 2 阶
第三种：2 阶 + 1 阶

所以我们用f(x)表示爬到第x 级台阶的方案数
f(x)=f(x−1)+f(x−2)

/**
 * 循环-实现
 * 复杂度分析
 * 时间复杂度：循环执行n 次，每次花费常数的时间代价，故渐进时间复杂度为O(n)
 * 空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为O(1)
 *
 * @param n
 * @return
 */
private static int climbStairsDG(int n) {
    int o, p = 0, q = 1;
    for (int i = 1; i <= n; i++) {
        o = p;
        p = q;
        q = o + p;
    }
    return q;
}


/**
 * 递归-实现
 *
 * @param n
 * @return
 */
public static int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}