#70 Climbing Stairs——Top 100 Liked Questions

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

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(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)  
> """
> 
>     def climbStairs(n):
>         """
>         :type n: int
>         :rtype: int
>         """
>         if not n:
>             return 0
>         if n == 1:
>             return 1
>         if n == 2:
>             return 2
>         if n > 2:
>             res = climbStairs(n - 2) + climbStairs(n - 1)
>         return res
> 
> """
> 
> 超时，但结果是对的  
> """

> """
> 
> 第二次：动态规划，res中保存当前路径个数，res\[i\]对应res\[i - 1\] + res\[i - 2\]  
> """
> 
>     class Solution(object):
>         def climbStairs(self, n):
>             """
>             :type n: int
>             :rtype: int
>             """
>             res = [1, 2]
>             if n == 1:
>                 return res[0]
>             if n == 1:
>                 return res[1]
>             for i in range(2, n):
>                 res.append(res[i - 1] + res[i - 2])
>             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.
> 
> """