leetcode_爬楼梯

2019-02-10

爬呀爬~

题目

假设你正在爬楼梯。需要 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 阶

分析

有点像排列组合的题目，但还真不知道python怎么写，感觉把P和C的具体公式写出来就好，一些大神直接联想到了斐波那契数列，佩服佩服，不过想从实际问题的角度去考虑一下，我们从动态规划的角度考虑（几天前刚了解233……），第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和，这么一想，欸，的确是斐波那契数列，明了多了

解法1—斐波那契

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = 0
        b = 1
        for i in range(n):
            print(b)
            a,b = b,a+b
        return b

解法2

执行用时: 52 ms, 在Climbing Stairs的Python3提交中击败了15.27% 的用户，神仙也太多了吧，想个好点的，怎么也要超过30%，哭了

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

其实思想是一样的，只不过少了很多次的解包操作，可以快很多，但我自己看上一种办法更爽

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2019/02/10/leetcode-%E7%88%AC%E6%A5%BC%E6%A2%AF/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！