According to my syllabus, this is a dynamic programming problem yet the explanation to the problem I’m supplied with is really confusing and not close to being understandable.
The problem is such:
You are required to give change equal to n
(n is a positive nonzero integer, not necessarily bigger than biggest coin) with a given set of k
different coins such that each coin has a positive nonzero “value”.
The problem is to find the combination with least amount of coins that is equal to n
.
The only method of solution I can come up with is the 'brute' approach, so if I have the set {k1,k2,k3}
of coins, I'll need to calculate f(n-k1), f(n-k2), f(n-k3)
and for each of f(n-k_i)
I'll have to calculate another 3 possibilities, which lead to exponential complexity.
However, I've read that this is possible to solve in O(n)
time, yet all explanations I've seen were really math-based and non-intuitive.
I’m really eager to understand this solution, so any source of information regarding this problem could assist in many ways.
Thanks!