How does a dynamic programming algorithm avoid the work associated with recomputation of values?
AnswerThe fibonacci numbers f0, f1, f2, ... are defined by
| f0 | = | 0 | |
| f1 | = | 1 | |
| fn | = | fn-1 + fn-2 (for n > 1) |
The following algorithm is based directly on this definition.
f(n)
if(n < 2) return n
else return f(n-1) + f(n-2)
Is that an efficient algorithm? If so, explain why. If not, explain why not and describe
how to make the algorithm efficient.
Answer
The coin changing problem is as follows. You are given a list of integer coin values c1, ..., ck, where c1 = 1 and c1 < c2 < ... < ck. You are also given a desired amount x of change, where x is a positive integer. The goal is to find out the fewest number of coins whose values total exactly x, where each coin must have one of the given values. You do not need to list the coins, only say how many are used.
For a given list of coin values, let C(y) be the smallest number of coins whose total value is exactly y. Then the goal is to determine C(x).
For example, suppose the coin values are 1, 5, 10 and 25. (So you have pennies, nickels, dimes and quarters.) You can make 30 cents as 25 + 5, so C(30) = 2 (for these coin values), and you can make 52 cents as 25 + 25 + 1 + 1, so C(52) = 4 (again, for these coin values).
Write recurrences for C(x). What is C(1)? What is C(x) for x > 1? You can make use of the given coin values c1, ..., ck.
Give an efficient algorithm to compute C(x) for a given positive integer x. If must work for any list that satisfies the requirements of the problem.