[LeetCode] 爬楼梯【70】

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

示例1

输入: n = 2
输出: 2
解释: 有两种方法可以爬到楼顶
         ① 1阶+1阶
         ② 2阶

示例2

输入: n = 3
输出: 3
解释: 有三种方法可以爬到楼顶。
         ①1阶+1阶+1阶
         ②1阶+2阶
         ③2阶+1阶

# 解法1
def climbStairs(n):
    if n <= 2:
        return n
    else:
        return climbStairs(n-1) + climbStairs(n-2)

# 解法2
def climbStairs(n):
    arr = [1,2]
    if n <= 2:
        return arr[n - 1]
    else:
        # n大于2
        for i in range(2,n):
            arr.append(arr[i - 1] + arr[i - 2])
        return arr[n - 1]

climbStairs(2) # 2
climbStairs(3) # 3