Describe a dynamic programming algorithm to solve the problem of giving change optimally for all A. Analyze its runtime.

Problem 5. Define the problem of giving change as follows: Given a sorted array A of n distinct, positive integers with A 11-1 and a positive integer u, return an array B of length n such that -1 A[ * Bli-u and ,1B[n] is minimized. A represents the different coins, u is the amount of money needing to be returned, B tells us how many of each kind of coin to use, and the restrictions on B ensure that the correct amount is returned and the number of coins used is minimized. For U.S. currency, for instance, A = [1, 5, 10, 25, 50, 100]. Then for u = 289, B = 4,0, 1,1, 1,2]. Note that AII] = 1 is included to ensure that there is always a solution Describe a greedy algorithm to solve this problem. Analyze its runtime. The greedy approach does not guarantee an optimal solution for all A. Give an example where the greedy algorithm would return a solution that uses at least 5 more coins than necessary