提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

leetcoe 斐波那契初探 70. Climbing Stairs

初探 70 那契 斐波
2023-06-13 09:16:43 时间

这个经典了， 我记得以前看过清华版数据结构第一章， 整章都是讲这个的。 写的非常不错， 可惜没有PYTHON版的， 希望什么时候出一版python的哈哈。 《天才基本法》里也有问这个上梯子的桥段。

题目，

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

非常经典的递归问题， 有两个递归基， 即 n== 1, 和 n ==2， n>2的情况都可以拆解成更低n的问题， 比如 f(n=3) = f(3-1) + f(3-2), 即在上三个台阶时候， 你是先上一个，还是先上两个。

f(n = 5) = f(4) + f(3) , f(4) = f(3) + f(2), f(3) = f(2) + f(1),

先看最直观的答案：

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

        return self.climbStairs(n-1) + self.climbStairs(n-2)

思路是对的， 但是n==44的时候就已经超时， 原因可以看上面f(n == 5)的分解， 太多重复冗余的计算。

让我们通过牺牲空间来换取时间， 有那么多冗余的， 那我们把已经算过的值记下来就好了，这里就用字典记 {n: steps}的组合：

class Solution(object):
    
    def climbStairs(self, n, memo = {}):
        """
        :type n: int
        :rtype: int
        """
        if n in memo:
            return memo[n]

        if n == 1:
            return 1
        if n == 2:
            return 2

        ans = self.climbStairs(n-1) + self.climbStairs(n-2) 
        memo[n] = ans
        return ans

虽然这里省略了重复计算， 但是重复查询次数依然很多， 那么让我们更近一步， 寻找空间和时间兼顾的， 在最终答案前， 先看动态规划 （https://blog.csdn.net/fuxuemingzhu/article/details/51290778）：

class Solution(object):
    
    def climbStairs(self, n, memo = {}):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        
        return dp[-1]

从这个动态规划中， 我们可以发现， 其实只有一位前和两位前的值， 需要存储，那么就可以简化成空间压缩DP， 或者叫迭代法之类的，

class Solution(object):
    
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """

        first = second = 1

        for n in range(n):
            first, second = second, first + second
            print(first,second)
        
        return first

迭代时一直往前，所谓的bottom-up。 递归时从最终问题往前回溯， 所谓的top-down

相关文章