我的零钱兑换问题递归缓存解法为何失效？请求技术排查

原解法思路 #

• 递归策略：每次递归有两个选择——多使用1枚当前面额硬币，或者不再使用当前面额硬币
• 预处理：将硬币面额按降序排序
• 缓存逻辑：用缓存存储已处理的剩余金额，认为优先尝试高面额组合就能缓存最优最小值

原代码实现 #

func coinChange(coins []int, amount int) int {
    sort.Slice(coins, func(i, j int) bool {
        return coins[i] > coins[j] 
    })
    cache := map[int]int{}
    var coinChangeDp func(i, target int) int
    coinChangeDp = func(i, target int) int {
       if target == 0 {
           return 0
       }
       if i >= len(coins) {
           return -1
       }
       cur := coins[i]
       if cur == target {
           cache[target] = 1
           return 1
       }
       cached, ok := cache[target]
       if ok {
           return cached
       }
       if cur < target {
           amt := coinChangeDp(i, target-cur) 
           if amt != -1 {
               amt = 1 + amt
           }
           otherWay := coinChangeDp(i+1, target)
           if otherWay == -1 && amt == -1 {
               return -1
           } else if amt == -1 {
               cache[target] = otherWay
               return otherWay
           } else if otherWay == -1 {
               cache[target] = amt
               return amt
           } else if amt < otherWay {
               cache[target] = amt
               return amt
           } else {
               cache[target] = otherWay
               return otherWay
           }
       }
       return coinChangeDp(i+1, target)
    }
    return coinChangeDp(0, amount)
}

失效原因分析 #

核心问题在于缓存的键仅使用了剩余金额target，忽略了当前可用的硬币索引i：

• 同一个剩余金额target，在不同的硬币索引i下（即能使用的硬币范围不同），最优解可能完全不同。比如当i更小（可以使用前面的高面额硬币）时，target的最优解可能比i更大（只能使用后面低面额硬币）时更优，但原代码会把第一次计算的target结果缓存，后续遇到相同target但不同i的情况直接复用错误值。
• 以测试用例coins=[357,239,73,52]、amount=9832为例，递归过程中会先处理到只能使用后面低面额硬币的场景，计算出某个target的解并缓存，之后当可以使用高面额硬币处理同一个target时，直接返回了之前的非最优解，导致最终结果错误。

修正方案 #

将缓存的键改为(i, target)的组合，区分不同硬币范围下的剩余金额最优解，具体实现如下：

func coinChange(coins []int, amount int) int {
    sort.Slice(coins, func(i, j int) bool {
        return coins[i] > coins[j] 
    })
    // 用[i, target]作为缓存键
    cache := map[[2]int]int{}
    var coinChangeDp func(i, target int) int
    coinChangeDp = func(i, target int) int {
       if target == 0 {
           return 0
       }
       if i >= len(coins) {
           return -1
       }
       key := [2]int{i, target}
       if val, ok := cache[key]; ok {
           return val
       }
       cur := coins[i]
       res := -1
       // 尝试使用当前硬币
       if cur <= target {
           sub := coinChangeDp(i, target - cur)
           if sub != -1 {
               res = 1 + sub
           }
       }
       // 尝试不使用当前硬币，切换到下一种
       sub2 := coinChangeDp(i+1, target)
       if sub2 != -1 {
           if res == -1 || sub2 < res {
               res = sub2
           }
       }
       cache[key] = res
       return res
    }
    return coinChangeDp(0, amount)
}

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