70_爬楼梯 滚动数组 动态规划 python

题目搬运者

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

思路 滚动数组

动态规划其实更像数学里面的找规律找公式，数列吧
以前一直学不会动态规划的原因是一提起动态规划就觉得高大上，从名字上引申，又对该知识点没有印象，糟里糟糕。
但是现在自己自动把 动态规划== 数列、找规律，就开窍了，学会了，觉得自己又可以了。
但这个题难度只是easy啊，我一开始用递归还直接超时了，很是尴尬。
然后还是看了官方用的滚动数组
这题和那个汉诺塔问题很像，是一类问题，想都没想，直接用了递归。

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

结果就是超时
下面这个就是滚动数组的用法，时间是O（n），空间又小，就是常数级别。
总之很漂亮了。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        lown1 = 1
        lown2 = 2
        res = 0
        if n ==1 :return 1
        if n ==2 :return 2
        for i in range(3,n+1):
            res = lown1 + lown2
            lown1=lown2
            lown2=res
        return  res