Leetcode - 爬楼梯

问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

---

示例:

• 输入： 2
• 输出： 2
• 解释： 有两种方法可以爬到楼顶。
• 1. 1 阶 + 1 阶
• 2. 2 阶

• 输入： 3

• 输出： 3
• 解释： 有三种方法可以爬到楼顶。
• 1. 1 阶 + 1 阶 + 1 阶
• 2. 1 阶 + 2 阶
• 3. 2 阶 + 1 阶

---

解答

/**
 * 动态规划问题
 * 到第一个台阶只有一种
 * 到第二个台阶有两种
 * 到第三个台阶的时候 是不是 以上之和？
 * 所以 F(N) = F(N-1) + F(N-1)  (N>=3)
 * 可以参考我之前的文章动态规划
 */
@Test
public void testClimbStairs() {
    System.out.println(climbStairs(8));
}


/**
 * 爬楼梯
 *
 * @param n
 * @return
 */
public int climbStairs(int n) {

    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    if (n == 2) {
        return 2;
    }

    int a = 1;
    int b = 2;
    int temp = 0;

    for (int i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }


    return temp;
}