LeetCode Climbing Stairs

70. 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?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

虽然是easy模式,但是是很好的一道题。问爬一个有n个台阶的楼梯,每次只能跨1步或者2步,共有多少种方案。 使用DP解决,假设前n个台阶共有dp[n]种方案,来了一个新台阶第n+1个台阶,那么这个台阶可以单独1步跨,则方案数为dp[n];也可以和第n个台阶合在一起一次性跨2步,则还剩n-1个台阶,所以方案数为dp[n-1]。综合起来就是dp[n+1]=dp[n]+dp[n-1],这其实就是斐波那契数列。
求斐波那契数列的第n项是一个经典问题,如果使用原始的递归求解,则会有很多重复计算,导致超时:

class Solution {
public:
    int climbStairs(int n)
    {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbStairs(n – 1) + climbStairs(n – 2);
    }
};

但是每次我们只需要前两项的数值,所以可以优化为:

class Solution {
public:
    int climbStairs(int n)
    {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int a1 = 1, a2 = 2, tmp;
        for (int i = 3; i <= n; i++) {
            tmp = a1 + a2;
            swap(a1, a2);
            swap(a2, tmp);
        }
        return a2;
    }
};

本代码提交AC,用时0MS。

Leave a Reply

Your email address will not be published. Required fields are marked *