LeetCode 70. 爬楼梯

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

class Solution:
    def climbStairs(self, n: int) -> int:
        #动态规划 方法版
        # if n == 1:
        #     return 1
        # if n == 2:
        #     return 2
        # if n == 0:
        #     return 0
        # return (self.climbStairs(n-1) + self.climbStairs(n-2))
        #动态规划 字典版
        dic = dict()
        dic[0] = 0
        dic[1] = 1
        dic[2] = 2
        for i in range(3, n+1):
            dic[i] = dic[i-1] + dic[i-2]
        return dic[n]