2.3h Dynamic Programming

Dynamic Programming (DP)

Dynamic Programming is an algorithmic technique used to solve problems by breaking them down into smaller overlapping subproblems, solving each subproblem only once, and storing its solution to avoid redundant computations. It consists of the following four steps:

1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
4. Construct an optimal solution from the computed information.

Examples

Rod Cutting

We can use dynamic programming to decide where to cut steel rods. We have a table giving the price $p_i$ that we charge for a rod of integer length $i=1,2,\dots ,n$ inches. The rod-cutting problem asks to determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces. Consider the following price chart:

$i$	1	2	3	4	5	6	7	8	9	10
$p_i$	1	5	8	9	10	17	17	20	24	30

Then, a rod of $n=4$ inches can be cut into four 1-inch pieces, two 2-inch pieces, a mix of a 2-inch piece and two 1-inch pieces, or a mix of a 3-inch and a 1-inch piece. It may also be sold uncut. For $n=4$, cutting the rod into two 2-inch pieces will yield the highest revenue.

How do we proceed with this problem using DP? Regard that any rod of length $n$ can be cut in $2^{n-1}$ different ways, since it may be cut from the left or the right side, or remain uncut. We can formulate the solution to this problem as
$r_n={\max }_{1\le i\le n}\{p_i+r_{n-i}\}.$