美文网首页
Climbing Stairs in python

Climbing Stairs in python

作者: 你过来啊2018 | 来源:发表于2018-03-04 10:10 被阅读0次

    题目链接

    https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/
    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

    解题思路

    到第n个台阶有两个情况:

    • 在第n - 1个台阶,迈一个台阶过去
    • 在第n - 2个台阶,迈两个台阶过去
      可以推断出:F(n) = F(n - 1) + F(n - 2)

    方法一:直接使用递归,验证结果超时

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

    方法二:不使用递归方法

    初始化一个N长度的数组,并全部初始化为1,从第2个元素(0开始计数)开始使用F(n) = F(n - 1) + F(n - 2)计算每个台阶的step数

    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            dp = [1 for i in range(n + 1)]
            for i in range(2, n + 1):
                dp[i] = dp[i - 1] + dp[i - 2]
            return dp[n]
    

    方法三:将方法二中的初始化数组去掉

    使用三个变量代替方法二中的初始化数组,
    注意点:要非常三个变量赋值次序

    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 1:
                return 1
            if n == 2:
                return 2
            
            first = 1
            second = 2
            res = 0
    
            for i in range(3, n + 1):
                res = first + second
                first = second
                second = res
    
            return res
    

    相关文章

      网友评论

          本文标题:Climbing Stairs in python

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