Blog of Pan Chen

What is dynamic programming

Dynamic programming is like divide-and-conquer method. It also solves problems by combining the solutions to subproblems.

But, dynamic programming applies when the sub-problems overlap (sub-problems share sub-sub-problems, in DAC, sub-problems are disjoint.)

Obivously, when sub-problems share sub-sub-problems, DAC does more work than necessary (not good).

What will dynamic programming (I will call it DC followingly) do? It saves the solutions to the sub-sub-problems in a table so that the solutions can be reused everytime it solves the same sub-sub-problems.

DC are usually applied to Optimization Problems – we want a solution with Optimal Value, either minimal or maximal. Note that the solutions may not be unique so we call it “an optimal solution” instead of “the optimal solution”.

Steps to develop a dynamic-programming algorithm

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 (only needed when we want the solution itself). ???

Some examples to explain the steps

Rot Cutting

What we want

a way to cut a rod into rods of smaller length that maximizes their total value.

Context

Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods.

Although typically, the larger the length is, the higher the price is, it doesn’t mean we don’t need any cutting to get higher revenue. See the following price table:

Length	1	2	3	4	5	6	7	8	9	10
Price	1	5	8	9	10	17	17	20	24	30

For example, for a rod of length 4. Cutting it into two 2-length smaller rods gives us the maximal revenue: 10. (We won’t know it unless we list all the ways to cut and compute each revenue.)

We can have a general solution to the optimal value.

It is recursion. For every , we mean at the first cutting, we cut it into sub-rods of length i and n-1. And obviously, the arguments to the MAX function have all the possible cases of the first cutting, and so we can get the optimal value after comparing all the sum of the optimal values of the sub-rod and the value of no-cutting-at-all.

When we computer the optimal values of the sub-rods, we may have the sub-problems which we have solved. For example, we will need the optimal values of rod of length 2, when we want the optimal values of both 3-length rod and 4-length rod. If we stored the solutions to the optimal values of 2-length rod, we don’t need to solve the problem (solution of optimal value of 2-length rod.)

Or even simpler

This, we only computes the optimal value of the right-hand remaining sub-rod. Why it works? Because we can view the left-hand sub-rod as part of the optimal solution.

The Algorithm

Not-efficient One

CUT-ROD(p, n)
  if n == 0:
     return 0
  q = -99999999999
  for i = 0 to n:
    q = max(q, p[i] + CUT-ROD(p[n-i]))
  return q

It is not efficient because we call CUT-ROD every time.

Efficitent One (Thanks to Dynamic Programming)

We store the solutions in memory. So, when meeting the same problem, we don’t need to recompute the solutions. It is an exmaple of time-temory de-off.

There are to ways to implement dynamic programming:

top-down with memoization (memorization)

it remembers what results it has computed previously.

MEMORIZED-CUT-ROD(p, n)
  let r[0, ..., n] be a new array
  for i = 0 to n
    r[i] = -9999999999999999999
  return MEMORIZED-CUT-ROD-AUX(p, n, r)

MEMORIZED-CUT-ROD-AUX(p, n, r)
  if(r[n] >= 0)  //has been solved before
    return r[n]
  if(n == 0)
    return 0
  else
    q = -9999999999999999999
      for i = 1 to n
        q = max(p, p[i] + MEMORIZED-CUT-ROD-AUX(p, n - i, r))
  r[n] = q
  return q

You can say the only difference between this version and the original CUT-ROD is the we “memorize” the optimal values.

bottom-up method

We solve each subproblem only once, and when wefi rst see it, we have already solved all of its prerequisite subproblems.

BOTTOM-UP-CUT-ROD(p, n)
  let r[0, ..., n] be a new array
  r[0] = 0
  for j = 1 to n
    q = -99999
    for i = 1 to j //solve the smaller problems first
      q = max(q, p[i] + r[j - i])
    r[j] = q
  return r[n] // r[n] is what we want

Subproblem graphs

It helps us understand the set of subproblems involved and how subproblems depend on each other.

Like this one

Restructing a solution

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
  let r[0, ..., n] and s[0, ..., n] be new arrays.
  r[0] = 0
  for j = 1 to n
    q = -99999
    for i = 1 to j //solve the smaller problems first
      if(q < p[i] + r[j - i]) //Found a better solution
        q = max(q, p[i] + r[j - i])
        s[j] = i //We should cut the left-hand-size to i at the first cut!
    r[j] = q
  return r and s // r[n] is what we want

PRINT-CUT-ROD-SOLUTION(p, n)
  (r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
  while n > 0
    print s[n]
    n = n - s[n]

1. Why return r and s: because here we want a solution. So we have to return the whole s to know what the first cutting is for each size (sub-problem).
2. Why n – s[n]: this is because for a rod of size n, the optimal value is reached when the first cutting is s[n], after first cutting, the remaining rod has size n – s[n].