$***$Write Code in Java$***$ And provide the instraction how to run the code.

Program Requirements

Design an algorithm by applying dynamic programming $($DP$)$ to solve the following problem and implement

your algorithm in Java.

You are planning for a canoe trip down a river. There are $n$ trading posts along the river, numbered

$1,2$dots,$n$ such that trading post $1$ is furthest upstream and trading post $n$ is furthest downstream. At any

of these trading posts, you can rent a canoe, which may be returned at any other trading post downstream.

The trip begins at trading post $1$ and ends at trading post $n.$ For each pair $(i,j)$ with iijjn$=4cn=51$:$,n=62$:$,n=7ii,$

which are elements above the main diagonal $of$ the matrix.

Your goal $isto$ find a cost sequence $of$ canoe rentals with the minimum total cost. $In$ the example

above, $an$ optimal solution has a total cost $is30,$ which $isto$

rent a canoe $at$ post $1$ and drop $it$ off $at$ post $2$ with a cost $of10,$

then rent a canoe $at$ post $2$ and drop $it$ off $at$ post $4$ with a cost $of20.$

Complete the Following Tasks

$a.(5$ points$)$ Complete the first two steps:

Step $1.$ Find a recurrence relation, including the base case$(s).$ Define clearly each variable and

function you use $in$ your recurrence relation.

Step $2.$ Count the number $of$ distinct subproblems based $on$ your recurrence relation.

$b.(16$ points$)$ Programming. Implement $in$ Java $to$ complete the following two steps:

Step $3.$ Set $upaDP$ table $to$ store solutions $to$ all the distinct subproblems.

Step $4.$ Trace the $DP$ table $to$ find a solution $to$ the original problem.

Your program should output the following:

$(1)$ The $DP$ table with each cell holding the optimal solution value $(minimum$ total cost $of$ rentals$)$ for

the corresponding subproblem;

$(2)$ The optimal solution value $(minimum$ total cost $of$ rentals$)$ for the original problem, which must $be$

a value from your $DP$ table.

$(3)An$ optimal solution $to$ the original problem: a sequence $of$ rentals $(with$ minimum total cost$),$

including the information $of$ where $to$ rent and drop off each canoe and the corresponding cost $of$

each rental.

Submit one $.$zip file including all source files

$c.(9$ points$)$ Run your program $on$ the following three cost matrices and insert screenshots $of$ your

program's output for each one. You will not get full credits for both parts $b$ and $cif$ any part $of$ your

program's output for these three instances $is$ incorrect.

$n=5,cost$ matrix $1$:$,n=6,cost$ matrix $2$:$,n=7,cost$ matrix $3$ :

For this assignment there were three $.txt$ files $iam$ providing $it$ belove, what $it$ had $in$ each $.txt1i,$ the

$costof$ renting a canoe $at$ trading post $itogo$ directly from $itoj(by$ dropping $it$ off $at$ trading post $j)is$

given. You may assume that all canoe rental costs are positive integers.

A sample cost matrix $is$ shown below $(withn=4).$ Note that there $is$ a valid cost value only for $i,$

which are elements above the main diagonal $of$ the matrix.

Your goal $isto$ find a cost sequence $of$ canoe rentals with the minimum total cost. $In$ the example

above, $an$ optimal solution has a total cost $is30,$ which $isto$

rent a canoe $at$ post $1$ and drop $it$ off $at$ post $2$ with a cost $of10,$

then rent a canoe $at$ post $2$ and drop $it$ off $at$ post $4$ with a cost $of20.$

Complete the Following Tasks

$a.(5$ points$)$ Complete the first two steps:

Step $1.$ Find a recurrence relation, including the base case$(s).$ Define clearly each variable and

function you use $in$ your recurrence relation.

Step $2.$ Count the number $of$ distinct subproblems based $on$ your recurrence relation.

$b.(16$ points$)$ Programming. Implement $in$ Java $to$ complete the following two steps:

Step $3.$ Set $upaDP$ table $to$ store solutions $to$ all the distinct subproblems.

Step $4.$ Trace the $DP$ table $to$ find a solution $to$ the original problem.

Your program should output the following:

$(1)$ The $DP$ table with each cell holding the optimal solution value $(minimum$ total cost $of$ rentals$)$ for

the corresponding subproblem;

$(2)$ The optimal solution value $(minimum$ total cost $of$ rentals$)$ for the original problem, which must $be$

a value from your $DP$ table.

$(3)An$ optimal solution $to$ the original problem: a sequence $of$ rentals $(with$ minimum total cost$),$

including the information $of$ where $to$ rent and drop off each canoe and the corresponding cost $of$

each rental.

Submit one $.$zip file including all source files

$c.(9$ points$)$ Run your program $on$ the following three cost matrices and insert screenshots $of$ your

program's output for each one. You will not get full credits for both parts $b$ and $cif$ any part $of$ your

program's output for these three instances $is$ incorrect.

$n=5,cost$ matrix $1$:$,n=6,cost$ matrix $2$:$,n=7,cost$ matrix $3$ :

For this assignment there were three $.txt$ files $iam$ providing $it$ belove, what $it$ had $in$ each $.txt$