Write a function named minCoins that accepts a reference to a vector of coin demoninations as integers, and a target integer value K, and uses dynamic programming to compute and return the minimum number of coins needed to produce exactly K cents.
For example, if the denominations are {1, 5, 10, 25} and the amount K is 30, the minimum coins are 2 (a 25-cent coin and a 5-cent coin).
If the denominations are {1, 5, 6, 9, 25, 50} and the amount K is 17, the minimum coins are 3 (two occurrences of the 6-cent coin and one of the 1-cent coin).
The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach.
You are allowed to construct any data structures (array, vector, set, map, etc.) necessary to store the data for your dynamic programming algorithm.
You are also allowed to define other "helper" functions if you like.
Your solution must also obey the following constraints:
-
Do not use recursion. Your solution must use dynamic programming instead.
You may assume that the coin denominations in the vector occur in ascending order, that no denomination will be negative, and that the vector contains no duplicates.
You may assume that you have an infinite number of each denomination of coin.
You may also assume that it is possible to make exactly the given amount of change with the given denominations of coins.
