【LeetCode】70. Climbing Stairs

深藏阁楼爱情的钟 2022-03-15 09:16 147阅读 0赞

#### Introduction ####

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. step + 1 step
    2. steps

Example 2:

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

#### Solution ####

实际上，这道题的结果是斐波那契数列，为了简介代码，我首先想到的是使用lambda表达式，结果，竟然超时了。。。  
Method 1  
使用lambda表达式构建斐波那契函数。

class Solution(object):
        def climbStairs(self, n):
            """ :type n: int :rtype: int """
            fib = lambda n:1 if n<=2 else fib(n-1)+fib(n-2)
            return fib(n+1)

[https://leetcode.com/submissions/detail/202039687/][https_leetcode.com_submissions_detail_202039687]  
Method 2  
直接使用斐波那契数列的通项公式进行计算。

class Solution(object):
        def climbStairs(self, n):
            """ :type n: int :rtype: int """
            from math import sqrt
            return int(sqrt(5)/5*((((1+sqrt(5))/2))**(n+1)-(((1-sqrt(5))/2))**(n+1)))

[https://leetcode.com/submissions/detail/202040369/][https_leetcode.com_submissions_detail_202040369]  
Method 3  
递归构建斐波那契函数。

class Solution(object):
        def climbStairs(self, n):
            """ :type n: int :rtype: int """
            a=1
            b=1
            def fib(n, a, b):
                while n != 0:
                    a, b = b, a+b
                    n -= 1
                return b
            return fib(n-1, a, b)

[https://leetcode.com/submissions/detail/202222009/][https_leetcode.com_submissions_detail_202222009]

#### Code ####

GitHub：[https://github.com/roguesir/LeetCode-Algorithm][https_github.com_roguesir_LeetCode-Algorithm]

*  更新时间：2019-03-01

[https_leetcode.com_submissions_detail_202039687]: https://leetcode.com/submissions/detail/202039687/
[https_leetcode.com_submissions_detail_202040369]: https://leetcode.com/submissions/detail/202040369/
[https_leetcode.com_submissions_detail_202222009]: https://leetcode.com/submissions/detail/202222009/
[https_github.com_roguesir_LeetCode-Algorithm]: https://github.com/roguesir/LeetCode-Algorithm