【LeetCode】70、爬楼梯

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.

• 中文：

  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

  每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

  注意：给定 n 是一个正整数。

• 示例

  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

解题思路

思路一

动态规划问题，直接递归，用$f (n)$表示到达第$n$阶时的方法数，共有两种爬楼方式（一次一阶，一次两阶），那么到达第$n$阶可以通过“到达第$n-1$阶后再走一次一阶”和“到达第$n-2$阶后再走一次两阶”两种方式，那么只需要考虑到达$n-1$阶和$n-2$阶各有多少种方法即可，即$f(n) = f(n-1) + f(n-2)$，终止条件为$f(1) = 1 , f(2)=2$。

代码提交

Python3，超时

时间复杂度：T(n) = O(1.618 ^ n)（1.618就是黄金分割，(1+5–√)/2(1+5)/2）。

空间复杂度取决于递归的深度，显然是O(n)。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

直接递归的方法重复计算太多，直接超时，将计算过的结果进行缓存，使用递归的方式，如下：

Python3，用时80ms，内存13.2M

时间复杂度是O(n)

空间复杂度是O(1)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        tempNum = [0,1,2]
        for i in range(3, n+1):
            tempNum.append(tempNum[i-1] + tempNum[i-2])
        return tempNum[n]

思路二

递归表达式及终止条件值符合斐波那契数列。其实跟上面的方法差不多。

代码提交

Python3，用时52ms，内存13.1M

时间复杂性：$O (n)​$

class Solution:
    def climbStairs(self, n: int) -> int:
        a = 0
        b = 1
        for i in range(n+1):
            a, b = a + b, a
        return a