题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

思路

最开始使用的是回溯的方法，但是时间效率地下没有通过，于是想到了动态规划的算法。对于i楼梯，到达其的方法有从i-1跨一步和i-2跨两步，因此到底i的方法就等于到达i-1的方法+到达i-2的方法

实现

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