【Leetcode】70. Climbing Stairs

经典的爬楼梯问题

方法1 DP

dp法,经典dp，注意初始值即可。
dp法是一种from bottom to top 的方法

class Solution1:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp = [1 for i in range(n+1)]
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return  dp[-1]

方法2 递归法

recursion 是一种from top to bottom 的方法
最原始的递归是这样写的，但是这样写会有大量的重复计算，当n比较大（比如40）的时候会超时

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

改进

我们可以将计算过的值存到dict中，再次使用的时候直接取即可

class Solution2:
    def climbStairs(self, n):
        self.dictionary = {}
        return self.helper(n)

    def helper(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        if (n-1) in self.dictionary:
            n_1 = self.dictionary[n-1]
        else:
            n_1 = self.helper(n-1)
            self.dictionary[n-1] = n_1
        if (n-2) in self.dictionary:
            n_2 = self.dictionary[n-2]
        else:
            n_2 = self.helper(n-2)
            self.dictionary[n-2] = n_2
        return n_1 + n_2

更简单的写法可以这样

class Solution2:
    def climbStairs(self, n):
        self.dictionary = {1:1, 2:2}
        return self.helper(n)
        
    def helper(self, n):
        if n not in self.dictionary:
            self.dictionary[n] = self.helper(n-1) + self.helper(n-2)
        return self.dictionary[n]

不显示的时候dict，我们可以使用python的装饰器lru_cache，来自动优化内存

from functools import lru_cache
class Solution2:
    @lru_cache(None)
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        if n == 2:
            return 2
        else:
            return self.climbStairs(n-2) + self.climbStairs(n-1)