每天一道力扣题: 70. 爬楼梯

爬楼梯问题是一道经典的动态规划入门题，其核心在于找到到达第n阶楼梯的方法数。以下是针对该问题的详细解答：

问题描述

假设你正在爬楼梯，每次你可以爬1个或2个台阶。问到达第n个台阶有多少种不同的方法？

解题思路

递归法：
基本情况：当n为1或2时，方法数分别为1和2。
递归关系：对于n>2的情况，到达第n阶的方法数等于到达第n-1阶的方法数加上到达第n-2阶的方法数，即f(n) = f(n-1) + f(n-2)。
优化：使用备忘录（Map）来存储已计算的结果，避免重复计算，提高效率。
迭代法：
初始化：对于n=1,2,3，直接返回n。
迭代计算：使用三个变量f1, f2, f3分别表示到达第n-2, n-1, n阶的方法数。通过循环更新这三个变量，最终f3即为所求。

代码实现递归法var climbStairs = function(n) { if (n <= 3) { return n; } let output = 0; const map = new Map(); if (map.get(n)) { return map.get(n); } output = climbStairs(n-1) + climbStairs(n-2); map.set(n, output); return output;};迭代法var climbStairs = function(n) { if (n <= 3) { return n; } let f1 = 1, f2 = 2, f3 = 3; for (let i = 4; i <= n; i++) { f1 = f2; f2 = f3; f3 = f1 + f2; } return f3;};复杂度分析

递归法：
时间复杂度：O(n)，由于使用了备忘录，每个子问题只计算一次。
空间复杂度：O(n)，用于存储备忘录。
迭代法：
时间复杂度：O(n)，通过一次循环完成计算。
空间复杂度：O(1)，仅使用了常数个额外变量。

示例

输入：n = 5
输出：8
解释：
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
1+2+2
2+1+2
2+2+1

总结

爬楼梯问题展示了动态规划的核心思想：将复杂问题分解为更小的子问题，并通过存储子问题的解来避免重复计算。递归法直观但可能效率较低，迭代法则更为高效。根据具体需求选择合适的方法。

您可能感兴趣问答

Collapsible

热门标签

热点问答