70. Climbing Stairs

题目描述和难度

  • 题目描述:

假设你正在爬楼梯。需要 n 步你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2

输出: 2

解释: 有两种方法可以爬到楼顶。

1.  1 步 + 1 步

2.  2 步

示例 2:

输入: 3

输出: 3

解释: 有三种方法可以爬到楼顶。

1.  1 步 + 1 步 + 1 步

2.  1 步 + 2 步

3.  2 步 + 1 步

思路分析

求解关键:

解释:爬楼梯问题,返回有多少种不同的方法爬完这 n 个台阶,Each time you can either climb 1 or 2 steps. 是这个问题的关键。 思考:分析问题过程中,我们发现这是一个递归问题,进而发现这个递归结构中存在许多重叠子问题,所以既可以使用记忆化搜索,也可以使用动态规划来解决。最终我们发现,这个问题其实和斐波那契数列问题完全等价。

版本1:不合格的递归版本,但是我们通过这个版本的思考可以帮助我们画出递归结构树,从而发现重叠子问题。

(插图说明这个问题的递归子结构数,标出重叠子问题。)

class Solution:

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

版本2:加入了缓存的递归版本

class Solution:
    memo = None

    def _climbStairs(self, n):
        if Solution.memo[n] != -1:
            return Solution.memo[n]

        if n == 0:
            return 1
        if n == 1:
            return 1
        Solution.memo[n] = self._climbStairs(n - 1) + self._climbStairs(n - 2)
        return Solution.memo[n]

    def climbStairs(self, n):
        Solution.memo = [-1] * (n + 1)
        return self._climbStairs(n)

版本3:在记忆化搜索的分析思路下,写出的动态规划版本。

思考过程:爬 0 个台阶,有 1 种爬法; 爬 1 个台阶,有 1 种爬法; 爬 2 个台阶,有 2 种爬法; 爬 3 个台阶,(2,1) + (1,2); 爬 4 个台阶,(3,1) + (2,2); 爬 5 个台阶,(4,1) + (3,2); 爬 6 个调节,(5,1) + (4,2); 以此类推,其中,(i,j)表示首先爬 i 个台阶的所有不同爬法,然后再爬 j 个台阶的不同爬法。

class Solution:

    def climbStairs(self, n):
        if n == 0:
            return 1
        memo = [-1] * (n + 1)
        memo[0] = 1
        memo[1] = 1
        for i in range(2, n + 1):
            memo[i] = memo[i - 1] + memo[i - 2]
        return memo[n]

参考解答

参考解答1