Leetcode 70.爬楼梯

Posted on |

70. 爬楼梯

题目

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

方法

原问题可以分解为子问题，原问题包含优化子结构性质：原问题的最优解是子问题的最优解的和

到达第i阶的两种方法：

  • 从第i-1阶跨越1步
  • 从第i-2阶跨越2步
    因此，到达第i阶的方法等于分别到达第i-1和i-2阶的方法的和

    方法1：动态规划 & 自底向上法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n==1:
                return 1
            dp=[0 for i in range(n)]
            dp[0],dp[1]=1,2
            for i in range(2,n):
                dp[i]=dp[i-1]+dp[i-2]
            return dp[-1]

Complexity Analysis

  • Time complexity : O(n). Single loop upto nn.
  • Space complexity : O(n). dpdp array of size nn is used.

    方法2：动态规划 & 自顶向下法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # Top Down Recursion (超时)
    class Solution(object):
        def climbStairs(self, n):
          # Base case:
          if n == 1:
            return 1
          if n == 2:
            return 2
          return self.climbStairs(n-1) + self.climbStairs(n-2)

参考资料