70. 爬楼梯

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

解法一：dp

由“累加”性质，很容易想到递推方程：dp[i] = dp[i-1] + dp[i-2]，dp[i]表示到达i层的方法总数，由于每次爬一步或两步，因此dp[i]只有可能由dp[i-1]和dp[i-2]而来。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n
        dp = [0] * (n+1)
        dp[1], dp[2] = 1, 2  #初始条件
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]