【Leetcode】070—Climbing Stairs

一、题目描述

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

示例：

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

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

二、代码实现

方法：动态规划

公式

f(0) = 1
f(1) = 2
f(k) = f(k-1) + f(k-2)

代码

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 1
        res = [0] * n
        res[0] = 1
        res[1] = 2
        for i in range(2,n):
            res[i] = res[i-1] + res[i-2]
        return res[-1]