[Solved]: How Dynamic programming can be used for Coin Change problem?

Problem Detail: 

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?

Asked By : Val

Answered By : Wandering Logic

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.

Also, memoization actually does a little more than lazy evaluation. Lazy evaluation caches the thunk for the expression assigned to a particular dynamic instance of a variable so that the thunk gets evaluated at most once. But memoization caches all expression evaluations, so if the expression is assigned to different dynamic variable instances you'll also only get a single evaluation. This requires a bit more machinery (you have to hash the arguments of the expression, and store the argument/result pair in a hash table.) If you were to rewrite the function in a lazy functional language (like Haskell) you wouldn't automatically get memoization benefits in this case.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28067