首页python上台阶问题递归

python上台阶问题递归

时间: 2023-09-23 14:12:30 AIGC 浏览: 190

Python上台阶问题可以使用递归的方法来解决。假设有N个台阶，每次可以迈1个或2个台阶，那么上N个台阶的方法数就等于上N-1个台阶的方法数加上上N-2个台阶的方法数，即f(N) = f(N-1) + f(N-2)。递归的代码如下： ```python def climb_stairs(n): if n == 1: return 1 if n == 2: return 2 return climb_stairs(n-1) + climb_stairs(n-2) ``` 然而，上述代码存在一个问题，就是在计算f(N)时，会重复计算f(N-1)和f(N-2)，导致效率低下，因此可以使用记忆化搜索的方法来优化。优化后的代码如下： ```python def climb_stairs(n, memo): if n == 1: return 1 if n == 2: return 2 if memo[n] == 0: memo[n] = climb_stairs(n-1, memo) + climb_stairs(n-2, memo) return memo[n] n = 10 memo = [0] * (n+1) print(climb_stairs(n, memo)) ``` 其中memo数组用于保存已经计算过的结果，避免重复计算。

阅读全文