At the Unseen University, several keen explorer$-$wizards recently reported

back with an astounding discovery: they have located a large forest of sapient

pearwood, an astonishingly rare material of immense value for constructing

high$-$quality sentient furniture. Since the discovery, the wizards have begun

their own enterprise selling lumber, Pearwood Industries $($PI$).$ Being somewhat

new to the lumber business, and knowing your algorithmic wizardry,

they come to you with a problem.

Given an m $\backslash$times n cross$-$section of lumber $($m and n are integers and the

units are in centimeters$),$ PI would like to cut the piece of lumber into some

number of smaller pieces for sale. Each section will be a rectangle with integer

dimensions. The value for any k $\backslash$times $$ piece can be looked up in constant time

and the value is not necessarily related to the area of the piece, as some

dimensions are simply in higher demand. For example, a $3\backslash$times $4$ piece might

be worth $$42$ while a $6\backslash$times $6$ piece might be worth $$8.$

Your wizarding friends have constructed a special saw that is capable of

making a cut $$ horizontally or vertically $$ across any rectangular section of

sapient pearwood at integer centimeter locations. $($Note that a cut is made

across the entire section of the given piece; no partial cuts are possible.$)$

Describe and analyze an efficient dynamic programming algorithm for

determining how to subdivide a given m$\backslash$times n piece to maximize the total value

of the resulting pieces. Use the process and writing style from Handout $2.$

For simplicity of exposition, you should describe an algorithm that returns

a number which is the maximum possible revenue. At the very end, in just

a few additional sentences, explain how you would modify your algorithm to

return the actual sequence of cuts that result in the pieces that make up this

optimal revenue.