Provide a dynamic programming solution to each problem by following the described steps.

You need to complete steps $($a$),($c$),($d$),$ and $($e$)$ for all $3$ problems, but it will suffice to complete steps $($b$)$ and $($f$)$ only for one of the problems:

Steps:

a$.$Identify the "last" decision you need to make to compute the value of the optimal solution.

For example, for rod cutting, the last decision we need to make is the length of the first cut we will make.

b$.$ Define and prove optimal substructure. This entails applying the statement "the solution to the larger problem cannot use suboptimal solutions to subproblems" to the specific problem in hand.

c$.$Define subproblems $($i$.$e$.,$ the table you are trying to compute$),$ express the value of the optimal solution for the overall problem in terms of the values of the optimal solutions to subproblems.

d$.$Formulate a recursive solution to compute the value of the optimal solution for subproblems.

Do not forget to specify the base cases$).$

e$.$Characterize the runtime of the resulting procedure assuming that you would implement your solution using a bottom$-$up procedure.

f$.$Provide the pseudo code of the bottom$-$up procedure you use to compute the value of the optimal solution, as well as the procedure for reconstructing the optimal solution. As an exercise that will help connect the abstract solution here to a real computer program, you may also want to implement this procedure using a programming language of your choice and test your code. But this is up to you and you do not need to submit anything in that regard.

$(2)$ We are given $n$ types of coin denominations with integer values $v_1,v_2,$dots,$v_n.$ Given an

integer $t,$ we would like to compute the minimum number of coins to make change for $t($i$.$e$.,$

we would like to compute the minimum number of coins that add up to $t,$ where repetitions

are allowed$).$ We know that one of the coins has value $1,$ so we can always make change for

any amount of money $t.$ For example, if we have coin denominations of $1,2,$ and $5,$ then the

optimal solution for $t=9$ is $5,2,2.$