美文网首页
leetcode 70 python 爬楼梯

leetcode 70 python 爬楼梯

作者: 慧鑫coming | 来源:发表于2019-01-31 13:44 被阅读0次

    传送门

    题目要求

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

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

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

    示例 1:
    输入: 2
    输出: 2
    解释: 有两种方法可以爬到楼顶。

    1. 1 阶 + 1 阶
    2. 2 阶

    示例 2:
    输入: 3
    输出: 3
    解释: 有三种方法可以爬到楼顶。

    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶

    思路一

    递归的解法,设有n阶楼梯(n>0),那么当爬到第n阶楼梯时,有2种方式,要么是爬1阶到n阶,要么爬2阶到n阶,若求阶公式为f(n),则f(n) = f(n-1) + f(n-2),终止条件是n==1 return 1, n==2 return 2

    →_→ talk is cheap, show me the code

    # 直接使用递归会AC超时,这里使用一个dict保存中间结果复用,勉强通过
    d = dict()
    
    class Solution:
        
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if not n:
                return 0
            if n == 1 or n == 2:
                return n
            if d.get(n):
                return d.get(n)
            res = self.climbStairs(n-1) + self.climbStairs(n-2)
            d[n] = res
            return res
    

    思路二

    递归的思想是从后往前,递过去归回来;我们找到了递归公式,也就能写出非递归的实现方式,当n=1时,有1中走法,当n=2时,有2种走法;有了这两个基础,就可以求出n=3时,有f(n-1) + f(n-2) =3种走法;(也就是斐波那契数列)

    →_→ talk is cheap, show me the code

    class Solution:
        
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if not n:
                return 0
            if n == 1 or n == 2:
                return n
            pre = 2
            prepre = 1
            ret = 0
            for i in range(3, n+1):
                ret = pre + prepre
                prepre = pre
                pre = ret
            return ret
    

    相关文章

      网友评论

          本文标题:leetcode 70 python 爬楼梯

          本文链接:https://www.haomeiwen.com/subject/nwsksqtx.html