LeetCode 322 Coin Change两种自顶向下解法对比及错误排查

问题核心 #

第二版代码的缺陷是记忆化缓存的设计不符合动态规划状态的无后效性要求，缓存值与当前递归路径的上下文绑定，无法通用。 #

具体错误原因 #

第一版代码的状态设计是正确的： #

第一版中_loop(remaining)函数的返回值固定表示「凑出金额remaining需要的最少硬币个数」，这个值只和remaining有关，和到达remaining的路径无关，符合无后效性要求，所以仅用remaining作为缓存键是完全正确的。

第二版代码的状态设计存在漏洞： #

第二版中_loop的返回值是「当前已用count枚硬币 + 凑出剩余remaining需要的最少硬币个数」，这个值和当前传入的count参数强相关，而count是随递归路径变化的上下文参数，不属于remaining的固有属性。
当不同递归路径到达同一个remaining值时，对应的count可能不同，你仅用remaining作为键存入缓存的结果，只是第一次到达该remaining时的路径对应的结果，不一定是全局最优的，后续其他路径到达同一个remaining时直接读取缓存，就会得到错误的非最优解。 #

错误场景示例 #

举个简单的测试用例：coins = [1,3,4], amount=6，最优解是3+3共2枚硬币：

1. 假设递归优先选面额1，路径走到1+1+1，此时remaining=3，传入的count=3，递归调用remaining-3=0返回3+1=4，memo[3]被存为4。
2. 后续递归走到选面额3的路径，remaining=3时传入的count=1，此时直接读取memo[3]得到4，总结果变成1+4=5，远大于正确的2，此时就会出现测试用例不通过的问题。

修复方案 #

如果要保留count参数的设计，需要把count也加入缓存键，但这样会大幅提升缓存的空间复杂度。更合理的方案是和第一版一样，让递归函数的返回值仅表示剩余金额对应的最少硬币数，去掉count参数，递归返回后再加1表示当前选的1枚硬币。

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