为何两种同复杂度的无界背包DP实现性能差异巨大？

核心问题：重复计算的量级天差地别 #

虽然两者理论时间复杂度都是O(amount*n)，但实际递归中产生的重复子问题数量完全不在一个量级，这是性能差距的根源：

多分支递归的致命缺陷 #

第一种实现每个节点分支数等于剩余硬币数，本质是枚举「选任意一种剩余硬币」的情况，但这种方式会大量重复计算相同的状态组合。比如凑金额5、硬币[1,2]时，它会走「选1再选2」和「选2再选1」两条不同递归路径，但这两条路径对应的是同一个组合（题目要求统计组合数，而非排列数）。每一次这种重复路径都会触发额外的方法调用，随着金额和硬币数量增大，总调用次数会爆炸式增长。

二叉递归的本质优化 #

二叉递归的思路是固定硬币的选择顺序：每个节点只做两种选择——「选当前硬币（无界特性支持重复选）」或者「不选当前硬币，直接跳过考虑下一种」。这种方式从根源上避免了组合的重复枚举，每一种合法组合只会被遍历一次，不会出现不同路径对应同一组合的情况，因此重复子问题的数量被降到最低，方法调用次数自然骤降。

分支因子与深度的权衡 #

虽然第一种分支因子大但深度小，但重复计算的代价远超过深度增加带来的开销。二叉递归的深度增加只是线性的（最多到amount/最小硬币值），但多分支递归的重复调用是指数级累积的——哪怕每个子问题多重复几次，在amount和n较大时，总调用次数会被放大到难以承受的程度。而二叉递归的所有调用都是必要的，没有冗余开销。

总结 #

两种实现的核心差异在于是否避免了组合的重复枚举：多分支递归没有限制选择顺序，导致大量冗余的子问题计算；二叉递归通过固定选择顺序，确保每个组合只被计算一次，因此实际运行中性能差距达到数量级。

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