# How Dynamic programming can be used for Coin Change problem?

As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of coin-change problem by truncating some search branches with caching.

Here is the problem, by the way

(define (count-change amount)
(cc amount 5))

(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))


I prefer the Scala translation

  def countWithoutRepetitions(s: Int, dimes: List[Int]): Int = {
if (s == 0) 1 else
if (s < 0 || dimes.isEmpty) 0
else dimes match {
case d :: ds => {countWithoutRepetitions(s, ds) + countWithoutRepetitions(s-d, ds)}
}
}


Odersky also asks for cache-based trimming algorithm in his course (pdf for those who are not enrolled). Yet, I do not understand what do people discuss at all.

The search tree never repeats itslef. It never calls the function with the same (sum, available_coins) arguments. What are you going to cache?

• dynamic programming / wikipedia – vzn Jun 29 '14 at 5:37
• Memoization is not a fancy name for lazy evaluation. They are orthogonal concepts: you can have either without the other. But I do agree that the wikipedia info on this is less than clear. – babou Jun 30 '14 at 13:25

Work an example. I worked through the Scheme version with the input 35 (and with the denominations of the coins as 1, 5, 10, 25, 50) and I'm seeing a ton of repetition in the search tree. (cc 5 1) has already come up 3 times and I'm only about half way through.
• @babou: I intended to say the opposite. In lazy functional evaluation if you assign an expression to a variable: x_0 = foo(bar) then foo(bar) will get evaluated at most once. But each additional assignment of the same expression to a different variable x_1 = foo(bar) may cause another evaluation. And x_0 and x_1 could be different static instances, or two different dynamic instances of the same static assignment statement. – Wandering Logic Jun 30 '14 at 12:58
• Assignment is a bad example for my question. Let's replace it by fum(foo(bar)). the function fum evaluates foo(bar) at most once for each call, lazily, but it can evaluate it twice in two distinct calls. To avoid a second evaluation of identical actual argument foo(bar) in two distinct calls, you need memoization. Do you agree with that? On the other hand, you can have memoization even when the function fum does not evaluate its argument lazily. I am only trying to say, there is not one that does more: they do different things, orthogonally. – babou Jun 30 '14 at 13:23