python - 将递归问题代码从 Python 转换为 Common Lisp

Question

我正在尝试将用 Python 编写的递归问题(第四个问题 here 有关详细信息，请参阅其 repo 页面)转换为(通用)Lisp
这是我为了可读性稍微编辑过的 Python 代码:

def coin(target,coins,res):
    # Default output to target
    min_coins = target
    # Base Case
    if target in coins:
        res[target] = 1
        return 1
    # Return a known result if it happens to be greater than 1
    elif res[target] > 0:
        return res[target]
    else:
        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:
            num_coins = 1 + coin(target-i,coins,res)
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                res[target] = min_coins
    return min_coins

target = 14
coins = [1,3,5]
res = [0]*(target+1)
print(coin(target,coins,res))
# => returns 4  ( 1 x 1, 1 x 3, 2 x 5)

这是我写的 Lisp 代码:

(defun coin (target coins res)
  (let ((min_coins target))  
    (if (some (lambda (x) (= target x)) coins)
        (progn
          (setf (aref res target) 1)
          1)
      (if (> (aref res target) 0)
          (aref res target)
        (dolist (i (remove-if-not (lambda (x) (<= x target)) coins))
          (let ((num_coins (1+ (coin (- target i) coins res))))
            (when (< num_coins min_coins)
              (setf min_coins num_coins)
              (setf (aref res target) min_coins))
            min_coins))))))

(coin 14 '(1 3 5) (make-array 15 :initial-element 0) )

当它被执行时，它会因为这个错误而停止:

The value
  NIL
is not of type
  NUMBER

如何安排它才能正确运行？
更新:
后 (trace coin)这是输出:

CL-USER> (coin 14 '(1 3 5) (make-array 15 :initial-element 0) )
  0: (COIN 14 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
    1: (COIN 13 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
      2: (COIN 12 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
        3: (COIN 11 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
          4: (COIN 10 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
            5: (COIN 9 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
              6: (COIN 8 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                7: (COIN 7 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                  8: (COIN 6 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                    9: (COIN 5 (1 3 5) #(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
                    9: COIN returned 1
                    9: (COIN 3 (1 3 5) #(0 0 0 0 0 1 2 0 0 0 0 0 0 0 0))
                    9: COIN returned 1
                    9: (COIN 1 (1 3 5) #(0 0 0 1 0 1 2 0 0 0 0 0 0 0 0))
                    9: COIN returned 1
                  8: COIN returned NIL
; Evaluation aborted on #<TYPE-ERROR expected-type: NUMBER datum: NIL>.

Answer 1

正确性
您的代码失败，因为您的 dolist 返回 nil .
你需要更换

(dolist (i (remove-if-not (lambda (x) (<= x target)) coins)) ...)

和

(dolist (i (remove-if-not (lambda (x) (<= x target)) coins) min_coins) ...)

效率
您正在使用 [] 在 Python 中创建免费列表在 for循环并在 Lisp 中使用 remove-if-not在 dolist .
众所周知的“足够聪明的编译器”应该能够消除它，但 Python 3 不够聪明，SBCL 也不够聪明。
风格
代码可读性很重要。我建议修改您的代码:

def coin(target,coins,res):
    # Default output to target
    # Base Case
    if target in coins:
        res[target] = 1
        return 1
    # Return a known result if it happens to be greater than 1
    if res[target] > 0:
        return res[target]
    # for every coin value that is <= than target
    min_coins = target
    for i in target:
        if i <= target:
            num_coins = 1 + coin(target-i,coins,res)
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                res[target] = min_coins
    return min_coins

和

(defun coin (target coins res)
  (cond ((find target coins)
         (setf (aref res target) 1))
        ((plusp (aref res target))
         (aref res target))
        (t
         (let ((min-coins target))
           (dolist (i coins min-coins)
             (when (<= i target)
               (let ((num-coins (1+ (coin (- target i) coins res))))
                 (when (< num-coins min-coins)
                   (setf min-coins num-coins)
                   (setf (aref res target) min-coins)))))))))