[LeetCode] 70. Climbing Stairs

正午 2020-01-07 PM 12℃ 0条

题目描述

原题链接
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 级楼梯, 每次可以选择走一步或者两步,一共有多少种走法

Note: Given n will be a positive integer.
【中文】给定的输入是是一个正整数 n

【例子一】:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps

【例子二】:

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

到第 n 级楼梯有两种走法 从 n-1 级走一步, 从 n-2 级走两步, 所以steps[n] = steps[n-1] + steps[n-2]
本质上就是一个斐波拉契数列

解法一: 动态规划

class Solution {
public:
    int climbStairs(int n) {
        vector<int> steps(n+1, 0);
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        steps[0] = 0;
        steps[1] = 1;
        steps[2] = 2;
        for(int i=3; i <=n; i++){
            steps[i] = steps[i-1] + steps[i-2];
        }
        return steps[n];
    }
};

解法二 递归

当处在 第 i 个楼梯的时候,剩下的走法是 i+1 到 n 的走法加上从第 i+2 个楼梯到 n 的走法
所以 steps[i到n] = steps[i+1 到 n ] + stes[i+2 到 n]
很直观的代码可以像下面这样写,但是这样写的复杂度是 O(2^n) , 因为 climStairsRec(low+1, heigh) 会重复计算很多相同的情况

class Solution {
public:
    int climbStairs(int n) {
        return climStairsRec(0, n);
    }
    int climStairsRec(int low, int heigh){
        if (low > heigh){
            return 0;
        }
        if(low==heigh){
            return 1;
        }
        return climStairsRec(low+1, heigh) + climStairsRec(low + 2, heigh);
    }
};

可以用空间来换时间,把计算过的都存下来,需要的时候直接取

class Solution {
public:
    int climbStairs(int n) {
       vector<int> memo(n+1, 0);
        return climStairsRec(0, n, memo);
    }
    int climStairsRec(int low, int heigh, vector<int>& memo){
        /**
        求从第 low 到 heigh 的走法
        **/
        if (low > heigh){
            return 0;
        }
        if(low==heigh){
            return 1;
        }
        if(memo[low]>0){
            return memo[low];
        }
        memo[low] = climStairsRec(low+1, heigh, memo) + climStairsRec(low + 2, heigh, memo);
        return memo[low];
    }
};
标签: LeetCode

非特殊说明,本博所有文章均为博主原创。

评论