Introduction-to-algorithms — dynamic programmimng

Dynamic programming typically applies to optimization problems in which we make a set of choices in order to arrive at an optimal solution. As we make each choice, subproblems of the same form often arise. Dynamic programming is effective when a given subproblem may arise form more than one partial set of choices.

The key technique is to store the solution to each such subproblem in case it should reappear.

Divide-and-conquer algorithms portion the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem — that is, when subproblems share subsubproblems.

In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly, solving the common subsubproblems.

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

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. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

When developing a dynamic-programming algorithm, we follow a sequence of four steps:

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

Step 1-3 from the basis of a dynamic-programming solution to a problem.

If we need only the value of an optimal solution, and not the solution itself, the we can omit step 4.
When we do perform step 4, we sometimes maintain additional information during step 3 so that we can easily construct an optimal solution.

Rod cutting

If an optimal solution cuts the rod into $k$ pieces, for some $1 \leq k \leq n$ , then an optimal decomposition

$n = i_1 + i_2 + \cdots + i_k.$

of the rod into pieces of lengths $i_1, i_2, \dots, i_k$ provides maximum corresponding revenue

$r_n = p_{i_1} + p_{i_2} + \cdots + p_{i_k}.$

More generally, we can frame the values $r_n$ for $n \geq 1$ in terms of optimal revenues from shorter rods:

$r_n = \max({p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, \dots, r_{n-1} + r_1})$

Since we don’t know ahead of time which value of $i$ optimizes revenue, we have to consider all possible values for $i$ and pick the one that maximizes revenue, we have to consider all possible values for $i$ and pick the one that maximizes revenue. We also have the option of picking no $i$ at all if we can obtain more revenue by selling the rod uncut.

We say that the road-cutting problem exhibits optimal substructure: optimal solution to a problem incorporate optimal solutions to related subproblems, which we may solve independently.

In a related, but slightly simper, way to arrange a recursive structure for the road curing problem we view a decomposition as consisting of a first piece of length $i$ cut off the left-hand end, and then a right-hand remainder of length $n - i$ .

$r_n = \max_{1 \leq i \leq n}(p_i + r_{n-i})$

In this formulation, an optimal solution embodies the solution to only one related subproblem — the remainder —rather than two.

Using dynamic programming for optimal rod cutting

Having observed that a naive recursive solution is inefficient because it solves the same subproblems repeatedly, we arrange for each subproblem to be solved only once, saving its solution. Dynamic programming thus uses additional memory to save computation time; it serves an example of a time-memory trade-off. The savings may be dramatics: an exponential-time solution may be transformed into a polynomial-time solution.

There are usually two equivalent ways to implement a dynamic-programming approach.

The first approach is top-down with memoization.

The second approach is the bottom-up method.

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

MEMOIZED-CUT-ROD-AUX(p, n, r)
  if r[n] >= 0
    return r[n]
  if n == 0
    q = 0
  else q = -\infty
    for i = 1 to n
      q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))
  r[n] = q
  return q

The bottom-up version is even simpler:

BOTTOM-UP-CUT-ROD(p, n)
  let r[0..n] be a new array
  r[0] = 0
  for j = 1 to n
    q = -\infty
    for i = 1 to j
      q = max(q, p[i] + r[j-i])
    r[j] = q
  return r[n]

Subproblem graphs

The subproblem graph for the problem embodies exactly this information. The subproblem graph has a directed edge from the vertex for subproblem $x$ to the vertex for subproblem $y$ if determining an optimal solution for subproblem $x$ involves directly considering an optimal solution for subproblem $y$ . We can think of the subproblem graph as a “reduced” or “collapsed” version of the recursion tree for the top-down recursive method, in which we coalesce all nodes for the same subproblem into a single vertex and direct all edges from parent to child.

The size of the subproblem graph $G =(V, E)$ can help us determine the running time of the dynamic programming algorithm. Since we solve each subproblem just once, the running time is the sum of the times needed to solve each subproblem. Typically, the time to compute the solution to a subproblem is proportional to the degree (number of outgoing edges) of the corresponding vertex in the subproblem graph, and the number of subproblems is equal to the number of vertices in the subproblem graph. In this common case, the running time of dynamic programming is linear in the number of vertices and edges.

Reconstructing a solution

Our dynamic-programming solutions to the rod-cutting problem return the value of an optimal solution, but they do not return an actual solution: a list of piece sizes. We can extend the dynamic-programming approach to record not only the optimal value computed for each subproblem, but also a choice that led to the optimal value. With this information, we can readily print an optimal solution.

Here is an extended version of BOTTOM-UP-CUT-ROD that computes, for each rod size $j$ , not only the maximum revenue $r_j$ , but also $s_j$ , the optimal size of the first piece to cut off.

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
  let r[0..n] and s[0..n] be a new array
  r[0] = 0
  for j = 1 to n
    q = -\infty
    for i = 1 to j
      if q < p[i] + r[j - i]
        q = p[i] + r[j - i]
        s[j] = i
    r[j] = q
  return r and s

The following procedure takes a price table p and a rod size n, and it calls EXTENDED-BOTTOM-UP-CUT-ROD to compute the array s[1..n] of optimal first-piece sizes and then prints out the complete list of piece sizes in an optimal decomposition of a rod of length $n$ :

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

Matrix-chain multiplication

Our next example of dynamic programming is an algorithm that solves the problem of matrix-chain multiplication. We can given a sequence (chain) $<A_1, A_2, \dots, A_n>$

Rod cutting

Using dynamic programming for optimal rod cutting

Subproblem graphs

Reconstructing a solution

Matrix-chain multiplication

Share this:

Leave a Reply Cancel reply