Skip to main content

Climbing Stairs

Climbing Stairs

描述

爬楼梯, 每次能爬一个台阶或者两个台阶, 一共有 n 个台阶, 一共有几种爬法

描述:
输入: 2
输出: 2

分析

由于2个台阶有两种爬法, 容易得出有以下的递推关系式:

\(
f(n) = f(n – 1) + f(n – 2)
\)

容易写出以下解法:

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

然后超时了, 分析很可能是因为重复计算了大量的 f(n) 导致, 用一个哈希表记录一下已经计算的值, 可以 ac, 答案如下

答案

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.m = {1:1, 2:2}
        return self.f(n)
    def f(self, n):
        if n in self.m:
            return self.m[n]
        self.m[n] = self.f(n - 1) + self.f(n - 2)
        return self.m[n]
打赏
微信扫一扫支付
微信logo微信扫一扫, 打赏作者吧~