070. Climbing Stairs

jay_tian 发布于2019-07-30 17:09 / 738人阅读

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:

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

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

Solution:

class Solution1:
    """
    递归做法
    """
    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)


class Solution2:
    """
    非递归做法
    """
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        pre_1_step = 1
        pre_2_step = 0
        count = 1
        for i in range(1, n+1):
            count = pre_1_step + pre_2_step
            pre_2_step = pre_1_step
            pre_1_step = count
        return count

class Solution:
    """
    非递归做法,比上一个方法快
    """
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        F = [0, 1]
        count = 1
        for i in range(n):
            count = F[0] + F[1]
            F[0] = F[1]
            F[1] = count
        return count

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42048.html

[Leetcode] Climbing Stairs 爬楼梯

摘要：递归法复杂度时间空间思路这题几乎就是求解斐波那契数列。最简单的方法就是递归。但重复计算时间复杂度高。代码递推法复杂度时间空间思路实际上我们求的时候只需要和的值，所以可以减少一些空间啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

tinyq 2019-08-14 12:26 评论0 收藏0
[leetcode] Climbing Stairs

摘要：实质就是把之前出现过的中间结果记录，下次再出现相同情况的时候，通过可以只用的时间复杂度得到。表示到达第层楼梯的不同走法。那么题目中每次可以选择走一步，或者两步，。从迭代公式可以知道，有两个，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

int64 2019-08-14 16:50 评论0 收藏0
746. Min Cost Climbing Stairs

746. Min Cost Climbing Stairs On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find mini...

skinner 2019-07-30 17:08 评论0 收藏0
[LintCode] Climbing Stairs II

Problem A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. Ex...

chengtao1633 2019-08-15 13:32 评论0 收藏0
[LintCode] Climbing Stairs

摘要：无需动规，无需额外空间，等同于菲波那切数列。当然噜，也可以动规，记住就好。 Problem 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 ...

jemygraw 2019-08-14 15:28 评论0 收藏0