在Guile中用动态规划解决硬币找零问题：如何生成正确组合列表？

一、生成有效硬币组合列表的修正 #

你的代码存在两个核心问题：终止条件处理不当，以及递归返回的列表嵌套未扁平化。以下是修正后的实现：

1. 生成所有排列（考虑硬币顺序，如(2,3)和(3,2)视为不同组合） #

(define (get-coins coins target)
  (cond
    ((= target 0) '(()))  ; 找到有效组合：空列表代表0个硬币，用列表包裹以便后续cons
    ((< target 0) '())     ; 金额为负，无有效组合，返回空列表
    (else
     ; 使用append-map替代map，将每个硬币生成的组合列表扁平化合并
     (append-map (lambda (coin)
                   ; 给每个递归得到的组合前添加当前硬币
                   (map (lambda (comb) (cons coin comb))
                        (get-coins coins (- target coin))))
                 coins))))

调用(get-coins '(2 3) 6)会返回：((2 2 2) (2 3) (3 2) (3 3))

2. 生成无重复组合（不考虑顺序，仅保留如(2,2,2)和(3,3)） #

如果需要避免重复排列，可通过限制递归时的硬币选择范围实现：

(define (get-coins coins target)
  (define (helper remaining-coins current-target)
    (cond
      ((= current-target 0) '(()))
      ((or (null? remaining-coins) (< current-target 0)) '())
      (else
       (append
        ; 选择当前硬币：继续用剩余硬币（含当前），金额减去硬币值
        (map (lambda (comb) (cons (car remaining-coins) comb))
             (helper remaining-coins (- current-target (car remaining-coins))))
        ; 不选当前硬币：递归处理剩下的硬币，金额不变
        (helper (cdr remaining-coins) current-target)))))
  (helper coins target))

调用(get-coins '(2 3) 6)会返回：((2 2 2) (3 3))，与你预期的结果一致。

二、动态规划求最少硬币数（高效解法） #

生成所有组合仅适合小金额场景，针对大金额，用递归+记忆化（Memoization）的动态规划更高效：

(define (coin-change coins amount)
  (define memo (make-hash-table))  ; 用哈希表缓存已计算的金额结果

  (define (min-coins target)
    (cond
      ((hash-ref memo target #f) => identity)  ; 命中缓存直接返回
      ((= target 0) 0)                          ; 0金额需要0个硬币
      ((< target 0) #f)                         ; 无效情况返回#f标记
      (else
       ; 收集所有有效硬币的递归结果，计算当前金额的最少硬币数
       (let ((candidates
              (filter identity
                      (map (lambda (coin)
                             (let ((res (min-coins (- target coin))))
                               (and res (+ res 1))))  ; 有效则加1（当前硬币）
                           coins))))
         (let ((result (if (null? candidates) #f (apply min candidates))))
           (hash-set! memo target result)  ; 存入缓存
           result)))))

  (let ((res (min-coins amount)))
    (if res res -1)))  ; 有效返回结果，无效返回-1

• 调用(coin-change '(2 3) 6)返回2（最少硬币数为2）
• 调用(coin-change '(2) 5)返回-1（无法凑成）

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