70-爬楼梯(Climbing Stairs)

秒速五厘米 2022-01-25 17:41 324阅读 0赞

题目描述

中文

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

英文

  1. You are climbing a stair case. It takes n steps to reach to the top.
  2. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
  3. Note: Given n will be a positive integer.

示例1

  1. 输入: 2
  2. 输出: 2
  3. 解释: 有两种方法可以爬到楼顶。
  4. 1. 1 + 1
  5. 2. 2

示例2

  1. 输入: 3
  2. 输出: 3
  3. 解释: 有三种方法可以爬到楼顶。
  4. 1. 1 + 1 + 1
  5. 2. 1 + 2
  6. 3. 2 + 1

题目分析

  • 我们先来简单分析:对于一个楼梯,我们一次只能上一阶或者两阶,所以这一步我们会有两种选择,如果我们选择了一阶,那么下一步同样会面临这个问题。所以我们就会得到这样一个公式:n阶总次数 = n-1阶总次数 + n-2阶总次数,这样一来用递归就可以很轻松的完成要求。

    class Solution {

    1. public int climbStairs(int n) {
    2. if(n == 1) //递归出口
    3. return 1;
    4. if(n == 2) //递归出口
    5. return 2;
    6. else
    7. return climbStairs(n-1) + climbStairs(n-2);
    8. }

    }

  • 可是对于递归我们都很了解,他的效率是十分低下的,那么能不能将他优化一下,使得效率有所提升呢?很明显是有的。

  • 对于普通递归,我们知道他效率低下的主要方面是因为大量数据的重复计算,这样我们就可以用一个数组把算过的数据存起来,如果下次仍然需要用到,我们就直接查找,这样效率就提高了很多。

    class Solution {

    1. public int climbStairs(int n) {
    2. int flag[] = new int[n + 1]; //flag存储计算过的台阶数的解决方案
    3. return climb_Stairs(n,flag);
    4. }
    5. public int climb_Stairs(int n, int [] flag) {
    6. if(n == 1 || n == 0)
    7. return 1;
    8. if(n < 0)
    9. return 0;
    10. if(flag[n] > 0)
    11. return flag[n];
    12. else
    13. flag[n] = (climb_Stairs(n-1,flag) + climb_Stairs(n-2,flag));
    14. return flag[n];
    15. }

    }

  • 到了这里,运行速度已经可以满足LeetCode上的时间限制了,可是有没有办法更快的求出这个题的解呢?答案是有的,那就是使用动态规划,对于动态规划不了解的可以点击这里,那么用动态规划怎么解决这道题目呢?

    1. 如果对动态规划有所了解,那么你一定清楚动态规划的核心步骤是什么。对,没错,就是找到规划方程。那么这道题的
    2. 规划方程到底是什么呢。





























阶数 步数
1 1
2 2
3 2+1=3
4 3+2=5
5 5+3=8
  • 到了这里是不是已经很明了了呢?他是不是让你想到了什么东西?没错,就是斐波那契数列,现在,我们来看这道题的题解。

    class Solution {

    1. public int climbStairs(int n) {
    2. if(n == 1)
    3. return 1;
    4. if(n == 2)
    5. return 2;
    6. int a = 1,b = 2,c = 0,i = 2;
    7. while(i < n){
    8. c = a + b;
    9. a = b;
    10. b = c;
    11. i++;
    12. }
    13. return c;
    14. }

    }

最后附上今天的python代码

  1. class Solution:
  2. def climbStairs(self, n: int) -> int:
  3. if n == 1:
  4. return 1
  5. if n == 2:
  6. return 2
  7. a = 1
  8. b = 2
  9. c = 0
  10. i = 2
  11. while i < n:
  12. c = a + b
  13. a = b
  14. b = c
  15. i += 1
  16. return c

今天的题目就到此为止了,我们下次再见。

发表评论

表情:
评论列表 (有 0 条评论,324人围观)

还没有评论,来说两句吧...

相关阅读