Haskell实现：如何对找零问题算法进行记忆化优化？

嘿，我明白你在HackerRank的找零问题上遇到的性能瓶颈了——递归解法虽然直观，但重复计算太多，大型测试用例肯定扛不住。咱们一步步来解决这个问题。

先分析原代码的核心问题 #

你的初始递归解法和重写版本都存在两个关键问题：

1. 缺失正确的基础情况：当目标金额n=0时，应该返回1（凑0元只有一种方法：不选任何硬币），但你的代码里没有处理这个场景，导致不必要的递归调用，甚至结果错误。
2. 无记忆化缓存：相同的(目标金额, 硬币组合)会被反复计算，比如计算makeChange 10 [1,2]时，makeChange 8 [1,2]会被多次调用，时间复杂度呈指数级增长。

如何用记忆化优化（附完整代码） #

在Haskell里，我们可以通过缓存已计算结果来避免重复计算，同时优化参数传递方式（用索引代替整个硬币列表）来提升缓存效率。下面是优化后的完整代码：

import Data.List (sort)
import qualified Data.Map as Map

-- 记忆化版本的找零函数
makeChange :: Int -> [Int] -> Int
makeChange target coins = go target 0
  where
    -- 先对硬币排序，方便跳过面值过大的硬币
    sortedCoins = sort coins
    coinCount = length sortedCoins
    
    -- 记忆化核心：用Map缓存(n, idx)的计算结果，idx表示当前处理到第几个硬币
    go = memoize calculate
    memoize f = \n idx ->
      case Map.lookup (n, idx) cache of
        Just val -> val
        Nothing -> let val = f n idx in
                   -- 用seq强制求值，避免惰性导致的内存泄漏
                   val `seq` Map.insert (n, idx) val cache `seq` val
    
    -- 初始化空缓存
    cache = Map.empty
    
    -- 实际递归计算逻辑
    calculate 0 _ = 1  -- 基础情况：凑0元只有1种方法
    calculate _ idx
      | idx >= coinCount = 0  -- 没有硬币可选，凑不出来
    calculate n idx =
      let coin = sortedCoins !! idx
      in if coin > n
         then go n (idx + 1)  -- 硬币面值过大，直接跳过
         else go n (idx + 1) + go (n - coin) idx  -- 两种情况：不用当前硬币 / 用至少一个当前硬币

-- 处理HackerRank输入：输入格式为 [目标金额, 硬币数量, 硬币1, 硬币2, ...]
main :: IO ()
main = interact $ show . processInput . map read . words
  where
    processInput (target:_:coins) = makeChange target coins
    processInput _ = 0  -- 处理异常输入

代码优化点详解 #

1. 修正基础情况：明确n=0时返回1，这是动态规划的核心基础，能让递归提前终止，减少无效调用。
2. 记忆化缓存：用Map存储(目标金额, 硬币索引)的计算结果，每次递归前先查缓存，存在则直接返回，不存在则计算后存入缓存。
3. 用索引代替硬币列表：相比传递整个硬币列表，整数索引作为缓存键更高效（比较、哈希成本更低），同时排序后的硬币能让我们快速跳过面值过大的选项。
4. 惰性求值控制：用seq强制缓存值的求值，避免Haskell惰性特性导致的内存泄漏。

更高效的数组缓存版本（可选） #

如果测试用例的目标金额和硬币数量都较大，用数组代替Map能获得更快的访问速度（O(1)随机访问）：

import Data.List (sort)
import Data.Array

makeChange :: Int -> [Int] -> Int
makeChange target coins = go target 0
  where
    sortedCoins = sort coins
    coinCount = length sortedCoins
    -- 创建二维数组缓存，范围覆盖所有可能的(n, idx)组合
    cache = array ((0,0), (target, coinCount)) 
              [ ((n, idx), calculate n idx) | n <- [0..target], idx <- [0..coinCount] ]
    go n idx = cache ! (n, idx)
    
    calculate 0 _ = 1
    calculate n idx
      | idx >= coinCount = 0
      | otherwise = let coin = sortedCoins !! idx
                    in if coin > n
                       then go n (idx + 1)
                       else go n (idx + 1) + go (n - coin) idx

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