Step-by-step Guides to reach Dynamic Programming Solution The following are ste

Step-by-step Guides to reach Dynamic Programming SolutionThe following are step-by-step guides to finish this lab. Answer all questions in red in this document, and modify/extend the code as instructed. In the end, submit this document on Blackboard, and the coin_change.cpp on autograder.Compile and run the starter code first, and understand the solutions given for UnlimitedCoinChange( ).To investigate whether dynamic programming can be used to improve its performance, we check if it has two characteristics: overlapping optimal substructure and overlapping subproblems. (Ref: CLR textbook, see the RodCuttingExplained reading posted on the weekly schedule page).* Optimal substructure refers to the fact that (optimal) solutions to a problem incorporate (optimal) solutions to related subproblems, which we may solve independently. Another way to put it is that the problem has a recursive solution.Can you write a formula for the mv, which denotes the minimum number of coins required to make value v with the given set of coins? If v cannot be expressed with the set of coins, mv is infinite.* Overlapping subproblem: Add cout statement to the function, to display a line such as the following whenever the function is called:UnlimitedCoinChange (value=14) calledCompile and run your program, and note all instances where UnlimitedCoinChange is called to solve a problem multiple times (a.k.a., overlapping subproblems) below:What are the overlapping subproblems you found?2. To avoid recomputing overlapping subproblems, we will use a table to store subproblem solutions.Analyze the UnlimitedCoinChange( ) function, as an algorithm, what are its input and output? Which input parameter(s) are not changed, and which input parameters are varying during the recursive calls?int UnlimitedCoinChange (const vector & coins, int value)b. Design the table to use following the guideline:The table used by dynamic programming provides a lookup: given a subproblem’s input, it tells us the subproblem’s solution.We typically use array or vector, where the index is the subproblem’s input, and the value of the array/vector element is the subproblem solution.vector subProblemSolutions; //subProblemSolutions[i] tells us the minimum number of coins that we can make value=i with; if a certain value cannot be expressed with the coins, its entry should be set to INT_MAXDraw the subProblemSolution table used for UnlimitedCoinChange(…, value=31,..) below. Show the size of the table, what’s stored in the table entry. Note that you don’t need to fill in the table’s entries, just illustrate using an example or two.vector coins{3, 5, 6, 10};3. Tabulation version:Write a new function, unlimitedCoinChange_Tabulation() that solves the problem using the tabulation approach. The following is the pseudocode://Return the minimum number of coins we need to use to make the given @value, assuming there are unlimited supplies for each type of coins given by @coins.int UnlimitedCoinChange_Tabulation (const vector & coins, int value){//1. Declare the table (see step 2 above)//2. Based upon the base cases from UnlimitedCoinChange, fill out the initial entries of the table//3. Write a for loop to solve all problems, from smallest (1) to largest (value)For (int cur_v=2; cur_v