#70 Climbing Stairs——Top 100 Liked Questions

ゝ一世哀愁。 2022-01-29 02:37 169阅读 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?

Note: Given n will be a positive integer.

Example 1:

  1. Input: 2
  2. Output: 2
  3. Explanation: There are two ways to climb to the top.
  4. 1. 1 step + 1 step
  5. 2. 2 steps

Example 2:

  1. Input: 3
  2. Output: 3
  3. Explanation: There are three ways to climb to the top.
  4. 1. 1 step + 1 step + 1 step
  5. 2. 1 step + 2 steps
  6. 3. 2 steps + 1 step

“””

第一次：递归，通过找规律发现，f(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)
“””

  1. def climbStairs(n):
  2.     """
  3.     :type n: int
  4.     :rtype: int
  5.     """
  6.     if not n:
  7.         return 0
  8.     if n == 1:
  9.         return 1
  10.     if n == 2:
  11.         return 2
  12.     if n > 2:
  13.         res = climbStairs(n - 2) + climbStairs(n - 1)
  14.     return res

“””

超时，但结果是对的
“””

“””

第二次：动态规划，res中保存当前路径个数，res[i]对应res[i - 1] + res[i - 2]
“””

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

“””

Runtime: 16 ms, faster than 97.24% of Python online submissions for Climbing Stairs.

Memory Usage: 11.8 MB, less than 44.01% of Python online submissions for Climbing Stairs.

“””

发表评论

表情：
评论列表 （有 0 条评论，169人围观）

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

相关阅读