Dynamic Programming

What is Dynamic Programming?

Let’s have a look at the definition on Introduction to Algorithm：

"Dynamic programming like the divide-and-conquer method, solves problems by combining the solutions to sub-problems.

Different from divide-and-conquer, dynamic programming applies when the sub-problems overlap — that is, when sub-problems share sub-sub-problems.

A dynamic programming algorithm solves each sub-sub-problems just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each sub-sub-problems.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value."

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 computed information.

Problems:

1 Rod cutting (IA – 15.1)

1.1 Analysis

Firstly we can frame the values rn for n >= 1 in terms of optimal revenues from shorter rods:

rn = max (pn, r1 + rn-1, r2 + rn-2, rn-1 + r1).

Here pn stands for the no-cut price and the rest combination means different way of cutting off.

We need to note that each cut will create two independent sub-problems so this is a optimal substructure. And we can get a simpler version of equation:

rn = max (pi + rn-1).

The trick to solve this problem in a high efficient is to only solve each sub-problem once and save its solution so that we can use them later rather than recompute them repeat. But it will use additional memory.

1.2 Two ways

1.2.1 Bottom-up with memorization
In this way, we just need to save the results of each sub-problems:

func(p, n)
let r[0...n] be a new array
for i = 0 to n
    r[i] = -infinity
return func-aux(p, n, r)

func-aux(p, n, r)
if r[n] >= 0
    return r[n]
if n == 0
    q = 0
else q = -infinity
    for i = 1 to n 
        q = max(q, p[i] + func-aux(p, n-i, r))
r[n] = q
return q

1.2.2 Bottom-up method
In this way, we sort the sub-problems by size and solve them in size order from smallest. So when we first see a sub-problem, we have already solved all of its prerequisite sub-problems:

func(p, n)
let r[0...n] be a new array
r[0] = 0
for j = 1 to n 
    q = -infinity
    for i = 1 to j
        q = max (q, p[i] + r[j-i])
    r[j] = q
return r[n]