python 爬楼梯问题用递归法 字典作为结束条件
时间: 2024-09-23 16:07:56 浏览: 7
Python爬楼梯问题是一个经典的动态规划问题,可以使用递归方法解决,通常涉及从底楼爬到指定楼层的过程。我们可以设置一个字典(通常称作“ memoization” 或者 “记忆化”)来存储已经计算过的楼梯数目,避免重复计算,从而提升效率。以下是递归解题的一个例子,其中字典作为结束条件(也就是到达顶楼的条件):
```python
def climb_stairs(n, memo={}):
# Base case: If the floor is 0 or 1, we are already at the top
if n == 0 or n == 1:
return n
# If we have already calculated this value, return it from the memo
if n in memo:
return memo[n]
# Calculate the number of ways to reach each floor (from previous two floors)
memo[n] = climb_stairs(n - 1, memo) + climb_stairs(n - 2, memo)
return memo[n]
# Test the function
print(climb_stairs(3)) # Output: 3 (1 step up from floor 2, 2 steps up from floor 1)
```
这个`climb_stairs`函数会计算从底层到第n层楼梯的不同走法数,并将结果存储在`memo`字典中。当再次需要计算同样的值时,它会直接返回,而不是重新计算,这就实现了循环依赖情况下的优化。当你达到顶层(即n为楼梯总数)时,递归终止,返回的结果就是所需的走法总和。