Exercise Corner to Corner Path $(15$ Points$)$

You are given an $nn$ table $p$ with natural numbers in each entry representing a profit. As with the

chessboard traversal problem discussed in class, the goal is to find a maximum profit path, subject to

these conditions:

The path must start in the upper left corner $($that is$,$ the square at position $1,1)$ and end at the

lower right corner $($position $n,n).$

A move from a square to the next on a path must go either to the right or down.

A path's profit is the total of the profits for the squares followed by the path.

Answer each of the following:

Define a function $q$ as a recurrence relation where $q(i,j)$ is the maximum profit attainable for

every path that ends at entry $i,j.$

As we've seen, one computes values for $q$ by using an $nn$ table called $q.$ For an

entry $q[i,j]$ in that table, specify which entries you need filled in before you can fill in $q[i,j].$

Specify an order for how to fill in the entries in $q$ given the previous answer.

Given the following values for the $p$ table, fill out the $q$ table. Write down the maximum

achievable path profit.