LeetCode整数拆分：Top-down DP参数传乘积为何出错？

先看两个实现的核心差异：错误版把乘积prod作为helper的参数，正确版把乘积计算逻辑放在返回值的乘法里，两者的dp存储的内容完全不同，这就是出错的关键。

错误实现的问题根源 #

错误版里的dp[total]存的是某次调用helper(total, prod)时得到的最终乘积，但这个值和传入的prod强绑定。同一个total，如果第一次带着prod=1进来，算出的结果存在dp里；第二次带着prod=2进来时，直接复用了之前的旧结果，但实际上此时应该用prod=2乘以后续拆分的最大乘积，而不是直接用之前的结果，这就导致了计算错误。

举个n=4的具体例子：

• 第一次调用helper(2, 1)时，算出结果是2，于是dp[2]=2。
• 后续调用helper(2, 2)时，因为total=2已经在dp里，直接返回2，但正确结果应该是2 * 2=4（此时整体拆分是2+2，符合至少两个数的要求），错误版直接复用旧值，导致最终结果偏小。

本质上，错误版混淆了拆分剩余部分的最大乘积和包含前面路径的总乘积：dp应该存储的是“从当前total出发，拆分剩下的数能得到的最大乘积”，而不是“从起点到当前total的乘积加上后续结果的总和”。

正确实现的逻辑 #

正确版的helper(total)返回的就是从total出发，拆分剩余部分的最大乘积，dp[total]存储的正是这个和前置路径无关的值：

• helper(2)返回的是拆分剩余2的最大乘积2。
• 调用helper(0)时，取j=2，计算helper(2)*2=2*2=4，这就是正确的最大乘积。

这样不管前面的路径如何，只要到了同一个total，都能复用dp里的“剩余部分最大乘积”，再乘以当前的j就能得到当前路径的总乘积，逻辑完全自洽。

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