You are offered a position as cash manager at a luxurious casino in Niagara Falls. Your first task is to check if it is possible to give a change or not given an unlimited supply of coins with denominations D = {d1, d2, . . . , dn} for an amount A. Armed with your experience from 282, you realize immediately this may be not possible for some denominations. The new boss asks for your help in devising a DP algorithm O(nA) that decides if the change is possible or not. Help the boss solve the problem by writing an algorithm for the solution. Hint: For0sA, you can defineT(s) = true if it is possible to make change for s using coins of the given denominations.

// Instructions: For this problem, you should argue the correctness of the algorithm, and analyze the order of running time. Please propose algorithms that are as efficient as possible. You will not get more than 2 points per problem for brute-force solutions.