第二十八天 Climbing Stairs

嗯，在成都的“中胜K书馆”刷leetcode，刚刚“编”完了晋升的PPT，心里还是挺虚的，还是刷两道题，开心开心吧

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

本质这道题，其实就是经典的“斐波纳切数列”
假设，n级台阶是有f(n)中走法
那么如果要跨到这第n级台阶的时候：
1、可以从n-1级跨，那么就有f(n-1)种走法
2、可以从n-2级跨，那么就有f(n-2)种走法
初时条件，1级和2级的走法数量是已知的，那么算法就很简单了

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n > 2:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

呵呵，不过很不幸，这个算法会TLE，那么就得把递归变成迭代了，也不难，哈哈

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        ret = [1,2]
        for i in range(2,n+1):
            ret.append(ret[i-1]+ret[i-2])
        return ret[n]

Over！