You need to enable JavaScript to run this app. Python求解Google Foobar楼梯问题:递归效率低如何优化?
优惠活动
大模型
产品
解决方案
定价
更多

Python求解Google Foobar楼梯问题:递归效率低如何优化?

问题本质与优化思路

这个问题本质是计算将n拆分为至少2个互不相同的正整数的分拆数(对应台阶严格降序、不重复、至少2级的要求)。你原来的递归是纯枚举无记忆,重复计算量随n呈指数级增长,完全可以通过动态规划将时间复杂度降到多项式级。

核心递推关系

定义状态dp(rem, max_allowed)为:剩余rem块砖,当前台阶最多能放max_allowed块砖时,能得到的合法方案总数。

  • 终止条件:
    • rem == 0:刚好用完所有砖,返回1(合法方案)
    • rem < 0或max_allowed <= 0:非法情况,返回0
  • 状态转移:所有方案可以分为两类:
    1. 当前级不使用max_allowed块砖:最多能用max_allowed-1块,对应方案数dp(rem, max_allowed-1)
    2. 当前级使用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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.28 19:06:04