Climbing Stairs in python

2018-03-04  本文已影响0人  你过来啊2018

题目链接

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个台阶有两个情况:

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

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
上一篇下一篇

猜你喜欢

热点阅读