70-爬楼梯（Climbing Stairs）

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

题目描述

中文

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

英文

  1. You are climbing a stair case. It takes n steps to reach to the top.
  3. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
  5. 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 条评论，321人围观）

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

相关阅读