70. 爬楼梯 [easy]

https://leetcode-cn.com/problems/climbing-stairs

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

通过次数222,021 | 提交次数446,502

Second Try

2020-06-15

也没看出来有快多少，不过前面的条件预处理有点繁琐了，别人都不这么写。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return 1
        prev2 = 1
        prev = 1
        for i in range(2, n+1):
            curr = prev + prev2
            prev2 = prev
            prev = curr
        return curr

执行用时 :20 ms, 在所有 Python 提交中击败了66.24%的用户
内存消耗 :12.6 MB, 在所有 Python 提交中击败了6.67%的用户

First Try

2020-06-15

动态规划每次纠结的点在于:

使用arr[n]数组还是arr[n+1]数组
arr[0]和arr[1]该怎么定义，是否提前返回

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

执行用时 :16 ms, 在所有 Python 提交中击败了85.92%的用户
内存消耗 :12.6 MB, 在所有 Python 提交中击败了6.67%的用户

70. 爬楼梯 [easy]​

Second Try​

First Try​

70. 爬楼梯 [easy]

Second Try

First Try