Haskell递归方案实现找零问题代码运行错误原因分析

1. lookup函数的索引偏移完全错误 #

当处理金额k时，传入go的Next attr结构中：

• attr的attribute字段存储的是金额k-1的计算结果
• attr的hole按层级依次存储k-2、k-3……0的计算结果
  也就是说lookup attr n实际获取的是金额(k-1) - n的结果，完全不是代码逻辑预期的金额n的结果。
  这个错误导致所有历史值查询都拿到了change 0 = 1的固定值，最终go的返回值刚好等于小于等于当前金额的硬币面额数量，你测试的change 10返回3，刚好对应[1,5,10]三个符合条件的面额，就是这个原因。

2. 业务逻辑与需求不匹配 #

若预期是计算最少硬币数： #

• 边界条件错误：凑0元需要的最少硬币数是0，不是当前代码的1
• 核心逻辑错误：应该对所有合法硬币的计算结果取最小值，而非求和，正确逻辑是最少硬币数 = 1 + min(所有剩余金额的最少硬币数)

若预期是统计不考虑顺序的合法组合数： #

• 存在重复计数问题：当前逻辑每次遍历所有硬币，会把1+5和5+1这类顺序不同的相同组合算作两种，需要限制每次只能使用不大于上一次选择的面额的硬币，避免排列重复计数

只需要修改change函数的go逻辑即可：

change :: Cent -> Int
change amt = histo go (expand amt)
 where
  go :: Nat (Attr Nat Int) -> Int
  go Zero = 0 -- 边界条件修正：0元需要0个硬币
  go curr@(Next attr) =
    let given = compress curr
        validCoins = filter (<= given) coins
        remaining = map (given -) validCoins
        (zeroes, toProcess) = partition (== 0) remaining
        -- 修正偏移：查询剩余金额m的结果，偏移量为 (given-1) - m
        getRes m = lookup attr ((given - 1) - m)
        candidates = (if not (null zeroes) then [1] else []) ++ map (\r -> 1 + getRes r) toProcess
     in minimum candidates

修复后运行change 10会返回正确结果1。

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