Python求解Google Foobar楼梯问题:递归效率低如何优化?
问题本质与优化思路
这个问题本质是计算将n拆分为至少2个互不相同的正整数的分拆数(对应台阶严格降序、不重复、至少2级的要求)。你原来的递归是纯枚举无记忆,重复计算量随n呈指数级增长,完全可以通过动态规划将时间复杂度降到多项式级。
核心递推关系
定义状态dp(rem, max_allowed)为:剩余rem块砖,当前台阶最多能放max_allowed块砖时,能得到的合法方案总数。
- 终止条件:
rem == 0:刚好用完所有砖,返回1(合法方案)rem < 0或max_allowed <= 0:非法情况,返回0
- 状态转移:所有方案可以分为两类:
- 当前级不使用
max_allowed块砖:最多能用max_allowed-1块,对应方案数dp(rem, max_allowed-1) - 当前级使用
max_allowed块砖:剩余砖为rem - max_allowed,下一级最多能用max_allowed-1块,对应方案数dp(rem - max_allowed, max_allowed-1)
因此递推式为:dp(rem, max_allowed) = dp(rem, max_allowed-1) + dp(rem - max_allowed, max_allowed-1)
- 当前级不使用
高效实现版本
1. 带记忆化的递归版本(直观易懂)
用lru_cache缓存已计算的状态,避免重复计算,适合快速实现:
from functools import lru_cache def solution(n): @lru_cache(maxsize=None) def dp(rem, max_allowed): if rem == 0: return 1 if rem < 0 or max_allowed <= 0: return 0 return dp(rem, max_allowed - 1) + dp(rem - max_allowed, max_allowed - 1) # 减去仅用1级台阶的非法方案(即n本身作为单级的情况) return dp(n, n) - 1
2. 自底向上的滚动DP版本(性能最优)
利用递推关系,结合01背包的空间优化思路,把空间复杂度压缩到O(n),n=1000也能瞬间算出结果:
def solution(n): if n < 3: # 至少2级台阶最少需要1+2=3块砖 return 0 # dp[rem] 表示当前剩余rem块砖的合法方案数,滚动数组优化 dp = [0] * (n + 1) dp[0] = 1 # 边界:剩余0块砖为1种合法情况 # 按允许的最大台阶高度从小到大遍历 for max_allowed in range(1, n + 1): # 逆序遍历剩余砖数,避免覆盖上一轮的计算结果 for rem in range(n, max_allowed - 1, -1): dp[rem] += dp[rem - max_allowed] # 减去单级台阶的非法方案 return dp[n] - 1
性能对比
- 原来的纯枚举递归时间复杂度为O(2^n),n=100时几乎无法算完
- 优化后的DP时间复杂度为O(n²),n=100时仅需1万次左右运算,耗时不到1毫秒
内容的提问来源于stack exchange,提问作者Giuppox
相关产品推荐
相关产品推荐

