PHP内存耗尽问题：不修改朴素算法如何降低内存占用？

嘿，我来帮你捋捋这个问题！Project Euler第31题的硬币找零组合数问题，朴素版本在目标和为100时正常运行，但调到200就内存耗尽，大概率是你的实现用了二维动态规划数组或者无记忆化的递归，导致内存占用飙升。咱们一步步说具体改动：

核心改动1：将二维DP压缩为一维DP #

这是最有效的内存优化手段，直接把内存复杂度从O(n×k)降到O(k)（n是硬币种类数，k是目标和）。

原理 #

原来的朴素二维DP会用dp[i][j]记录「用前i种硬币凑出金额j的组合数」，但实际上计算第i种硬币的状态时，只需要用到第i-1种硬币的结果，而且可以通过正序遍历金额来覆盖旧值，不需要保留所有历史状态。

代码对比 #

原来的二维朴素实现（内存占用高）

coins = [1, 2, 5, 10, 20, 50, 100, 200]
target = 200
# 创建二维数组，共8×201个元素
dp = [[0]*(target+1) for _ in range(len(coins)+1)]
dp[0][0] = 1  # 初始状态：0种硬币凑0元只有1种方法

for i in range(1, len(coins)+1):
    coin = coins[i-1]
    for j in range(target+1):
        dp[i][j] = dp[i-1][j]  # 不使用当前硬币的情况
        if j >= coin:
            dp[i][j] += dp[i][j - coin]  # 使用当前硬币的情况

print(dp[len(coins)][target])

优化后的一维DP实现（内存占用极低）

coins = [1, 2, 5, 10, 20, 50, 100, 200]
target = 200
# 只需要一维数组，共201个元素
dp = [0]*(target+1)
dp[0] = 1  # 初始状态不变

for coin in coins:
    # 从coin值开始遍历，避免重复计算同一硬币的多次使用
    for j in range(coin, target+1):
        dp[j] += dp[j - coin]

print(dp[target])

核心改动2：替换无记忆化递归为迭代实现 #

如果你的朴素算法是用递归实现的，无记忆化的递归会重复计算大量相同子问题（比如凑199、198的组合数会被反复调用），不仅耗时，还会导致栈溢出或堆内存被大量临时计算结果占满。

优化方向 #

• 要么给递归加记忆化缓存（比如用字典或数组存储已经计算过的子问题结果），避免重复计算；
• 更优的是直接改成上面的迭代式一维DP，完全避开递归栈的内存开销，同时效率更高。

额外小优化：清理不必要的中间变量 #

检查你的代码，有没有存储一些无关的中间结果（比如所有可能的组合列表），这些完全没必要——咱们只需要最终的组合数，不需要记录具体组合，删掉这些冗余数据结构能进一步降低内存占用。

其实核心思路就是只保留必要的状态，砍掉所有不需要存储的历史数据，这样别说目标和是200，就算调到10000也不会出现内存耗尽的问题～

内容的提问来源于stack exchange，提问作者tjomtjom