LeetCode 70. 爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

例：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1.1 阶 + 1 阶
2.2 阶

方法一

思路同 509. 斐波那契数，因为爬楼梯的方法和斐波那契数的计算方式相同。爬到第一阶有一种方法，一阶；爬到第二阶有两种方法，一阶 + 一阶和两阶；爬到第三阶有三种方法，一阶 + 一阶 + 一阶、一阶 + 两阶和两阶 + 一阶，即爬到第一阶后再爬两阶会到第三阶，或爬到第二阶后再爬一阶会到第三阶。那么我们可以得知爬到第三阶的方法的数量为爬到第一阶和爬到第二阶的方法数量和

class Solution(object):
    def climbStairs(self, n):
        if n == 1:
            return n
        a, b = 1, 2
        temp = 0
        for i in range(2, n):
            temp = b
            b = a + b
            a = temp
        return b

方法二：动态规划

思路同 377. 组合总和 Ⅳ

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        m = 2
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if i >= j:
                    dp[i] += dp[i-j]
        return dp[-1]

参考

代码相关：https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html