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?