2. Another classic problem regarding dynamic problem is Coin Change'. In this problem, there are n types of coins of value A1, A2, ..., An. You have to find if it is possible to make a total of Sum value using these coins. You can take each coin as many times as you want. a) One way to think about this problem is to notice that to make a total of Sum value using using coins of value A1, A2, ..., An, there are 2 scenarios: Not using the coin An even once. In that case, the total Sum now has to be constructed using coins of value A1, A2, ...,A(n-1). Using the coin An at least once. In that case, the total Sum An now has to be constructed using coins of value A1, A2,..., An i. Can this way of thinking be used to engineer a dynamic-programming solution to solve this problem? If so, please come up with an equation to solve the problem using sub-problems. Show how sub-sub-problems may overlap. ii. If you had to make a DP table, what would the rows and columns of that table correspond to? iii. Imagine, the coins you are provided are of values 2, 5, 10, 50, 100, 200, 501, 997. Can you make a DP table to find out if the value 252 can be constructed using these coins or not? You can write code in your computer to generate this DP table. iv. Using the same sets of coins (2, 5, 10, 50, 100, 200, 501, 997), can the value 10 be con- structed? Use the DP table you already constructed in the previous answer. v. What is the asymptotic run-time (big-O) of this approach