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.

$(3)$ Given two strings $x=$ and $Y=,$ the edit distance between

$x$ and $Y$ is defined as the minimum number of edit operations $($replacement$,$ insertion, or

deletion of a character$)$ required to convert $x$ to $Y.$ For example, the edit distance between

$x=$ esteban and $Y=$ stephen is $4,$ comprising of $1$ deletion $(e),1$ insertion $(h),$ and $2$

replacements and $ae).$ We would like to compute the edit distance between two

given strings.