题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解题
1.解法一：动态规划
思路
当n=1时，有1种方法，就是走一次1阶
当n=2时，有2种方法，就是走两次1阶或者走一次2阶
当n=3时，有3种方法，就是走三次1阶；走一次2阶，然后走1阶；走一次1阶，然后走2阶
......上楼梯，最后一步要么是走2阶，要么走1阶，如果是走1阶，说明此时正处于第n-1阶的位置；
如果是走2阶，说明此时正处于第n-2阶的位置。
因此，到达第n阶楼梯的所有方法数，恰好包含了从第n-1阶和第n-2阶转移过来的所有可能情况，所以它们的数量之和就等于到达第n阶楼梯的方法数。
数学公式可以表示为：F(n) = F(n-1) + F(n-2)。
算法复杂度
时间复杂度：O(n)，其中 n 是楼梯的阶数。
因为代码中的循环是基于阶数 n 的，只遍历了从3到n的每一个阶数，总共进行了 n - 2 次计算。每次计算所需的时间是常量级别的，所以总的时间复杂度为线性时间。
空间复杂度：O(1)，这里只用了常数个变量作为辅助空间
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
n1,n2=1,2
for i in range(3, n+1):
res = n1+n2
n1 = n2
n2 = res
return res2.解法二：递归
思路
根据F(n) = F(n-1) + F(n-2)，使用递归的方式来解决
算法复杂度
时间复杂度： O(2^n)，其中 n 是楼梯的阶数。
由于每一次递归都会产生两个新的递归调用，并且每次调用都是对之前计算过的子问题进行重复计算，因此时间复杂度是指数级别的。
空间复杂度：O(n)，其中 n 是楼梯的阶数。
递归调用会占用堆栈空间来保存中间状态。在最坏的情况下，递归树的深度将达到 n，因为每次递归调用都会创建一个新的堆栈帧。所以，空间复杂度为 O(n)。
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
else:
return self.climbStairs(n - 1) + self.climbStairs(n - 2)算法优化
思路
为了提升效率，结合记忆化搜索（Memoization）来缓存已计算过的子问题结果。
记忆化搜索（Memorization）是一种利用程序设计中的空间换时间策略，通过存储（或记忆）先前计算过的结果来避免同一子问题的重复计算，从而优化递归算法效率的技术。在解决动态规划问题时，记忆化搜索常常被用来加速那些具有重叠子问题的递归算法。
记忆化搜索的主要步骤包括：
1.定义一个数据结构（通常是数组或字典）来存储子问题的解。
2.在递归调用函数之前，首先检查是否已经计算过该子问题的解，并且该解已经被存储在记忆结构中。如果已经计算过，则直接返回存储的解。
3.如果子问题尚未解决，则计算其解，并将结果存储在记忆结构中，然后再返回该结果。
算法复杂度
时间复杂度： O(n)，其中 n 是楼梯的阶数。
在记忆化搜索中，每个子问题只会被计算一次，并且存储在记忆化字典中供后续查找。所以，对于每个阶数，我们都只需一次计算，故时间复杂度降为了线性时间，即 O(n)。
空间复杂度： O(n)，其中 n 是楼梯的阶数。
记忆化搜索需要存储每个子问题的解，即每个阶数对应的到达该阶数楼梯的方法数。因此，空间复杂度取决于楼梯的阶数 n，因为在最坏情况下，我们需要存储从0阶到n阶的所有结果，所以空间复杂度为 O(n)。
class Solution:
def climbStairs(self, n: int) -> int:
memo = {} # 初始化记忆化字典
def dfs(n):
if n <= 2:
return n
if n not in memo:
memo[n] = dfs(n - 1) + dfs(n - 2) # 记忆化，存储子问题的解
return memo[n] # 若已计算过，则直接从字典中获取结果
return dfs(n)
