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."
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.
1 Rod cutting (IA - 15.1)
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 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]