Coding for Interviews Issue #18 challenge: dynamic programming

change-maker.lisp

(defun change-combinations (amount denominations)
  "Return the number of (orderless) ways change can be made for integer AMOUNT
  given a list of integer DENOMINATIONS."
  (let ((dyntable (make-array (1+ amount) :initial-element 0)))
    (setf (elt dyntable 0) 1)
    (loop for denom in denominations
          do (loop for dyndex from denom to amount
                   do (incf (elt dyntable dyndex)
                            (elt dyntable (- dyndex denom)))))
    (elt dyntable amount)))

(defun csv-to-ints (csvstring)
  "Return a list of integers given a string of comma-separated values.
  Input presumed valid (whitespace is okay)."
  (let ((strvals (loop for i = 0 then (1+ j)
                       as j = (position #\, csvstring :start i)
                       collect (subseq csvstring i j)
                       while j)))
    (mapcar #'parse-integer strvals)))

(let ((coins (csv-to-ints (read-line)))
      (amount (parse-integer (read-line))))
  (print (change-combinations amount coins)))

(In practice, though, you'd probably prefer to install CL-UTILITIES and use SPLIT-SEQUENCE to get that list, and maybe do more string cleanup.)