The 5 steps to help solve this problem:

Step 1: What are the overlapping subproblems?

Step 2: Construct a matrix

Step 3: Initialize the matrix (for the simplest subproblems)

Step 4: Find the optimal substructure and complete table

Step 5: Identify solution (what are you returning?)

Consider the following Coin Change Problem: Given: A set S of n positive distinct integers as coin denominations S={d1,d2,d3,,dn} where d1=1 A positive integer B Question: Find the minimum number of coins to make change of B using denominations set S. Example: S={1,5,10,25} B=80 The minimum number is 4 ( 3 quarters and 1 dime). Design a Dynamic Programming Algorithm to solve the problem and analyze its running time. Your algorithm must clearly state the 5 steps we learned in class. And you must analyze its running time