# 4.3. Concepts of Dynamic Programming

Top-down → Bottom-up

• When the divide-and-conquer approach produces an exponential algorithm where the same sub-problems are solved iteratively,
  • 1. Take the recursive relation from the divide-and-conquer algorithm, and
  • 2. replace the recursive calls with table lookups by recording a value in a table entry instead of returning it.
• Three elements to consider in designing a dynamic programming algorithm
  • Recursive relation
    • Optimal substructure
  • Table setup
  • Table fill order
  • B(i,j)=B(i-1,j-1) + B(i-1,j) if 0<j<i
  • B(i,j)=1 if j=0 or j=i

# Application of DP

# 4.3.1. The Manhattan Tourist Problem

• Courtesy of [Jones & Pevzner 6.3]
• Problem:
  • Given two street corners in the borough of Manhattan in New York City, find the path between them with the maximum number of attractions, that is, a path of maximum overall weight.
  • Assume that a tourist may move either to east or to south only
• A brute force approach
  • Search among all paths in the grid for the longest path!
• A greedy approach
  • 다음 강의 주제
• A formal description of this problem
  • Given a weighted graph (grid) G of size (n, m) with two distinguished vertices, a source (0, 0) and a sink (n, m), find a longest path between them in its weighted graph. (0, 0)
• An example grid of size (4, 4)
  • 
• A possible selection determined by a greedy approach
  • 
• Basic idea
  • How can you use the solutions of smaller problems to build a solution of a problem?
    • 
  • A given optimization problem can be constructed efficiently from optimal solutions of its subproblems.
    • → optimal substructure
    • 
• Optimal substructure : S_{n,m} =?
  1. i,j \geq 1
  • S_{i,j} = \max(S_{i-1,j}+W({(i-1,j)},{(i,j)}), S_{i,j-1}+W({(i,j-1)},{(i,j)}))
  2. i=0, j=1,2,...,n
  • S_{0,j} = S_{0,j-1}+W({(0,j-1)},{(0,j)})
  3. j=0, i=1,2,...,m
  • S_{i,0} = S_{i-1,0}+W({(i-1,0)},{(i,0)})
  4. i=j=0
  • S_{0,0} = 0
• Table setup and fill
  • 
• Pseudocode
  • 
• Given a (n, m) grid, what is the time complexity T(n, m)?
• So far, we have found the cost of the longest path from source to each vertex in the grid.
• Then, how can you print out the actual optimal path from source to sink?
  • 

# 4.3.2. Chained Matrix Multiplication

• [Neapolitan 3.4]
• In general, to multiply an a x b matrix with a b x c matrix using the standard method, it is necessary to do abc elementary multiplications.
  • 
• Problem
  • Determine the minimum number of elementary multiplications, needed to multiply n matrices where $ A_i \in R^{d_ \times d_i}$
• Examples: A_1 (20 \times 2) \bullet A_2 (2 \times 30) \bullet A_3 (30 \times 12) \bullet A_4 (12 \times 8)
  • A_1: 20 \times 2, A_2: 2 \times 30
  • $A_1(A_2(A_3 A_4)) : 30 \times 12 \times 8 + 2 \times 30 \times 8 + 20 \times 2 \times 8 = 3,680 $ multiplications
  • (A_1 A_2)(A_3 A_4) : = 8,880 multiplications
  • A_1((A_2 A_3 )A_4) : = 1,232 multiplications
  • ((A_1 A_2)A_3 )A_4 := 10,320 multiplications
  • (A_1(A_2 A_3 ))A_4 := 3,120 multiplications
  • The order of multiplication is very important!
    • (a \times b) \times c = a \times (b \times c)

# 4.3.3. Dynamic programming approach

• Definition

  • M(i, j) : the minimum number of multiplications needed to multiply A_i through A_j (i \leq j )
  • 

• Optimal subtructure

• Example: M(2, 7)

  • M(2,7) = \min_{2\leq k \leq 6}{\{ M(2,k) + M(k+1,7)+d_1 d_k d_7}\}

  j/i	1	2	3	4	5	6	7	8
  1	0
  2		0
  3			0
  4				0
  5					0
  6						0
  7							0
  8								0

  j/i	1	2	3	4	5	6	7	8
  1	0
  2		0
  3			0
  4				0
  5					0
  6						0
  7							0
  8								0

• Table fill order

  for (i = 1; i <= n; i++)
      M[i][i] = 0;
  for (g = 1; g <= n - 1; g++)
      for (i = 1; i <= n - g; i++)
      {
          j = i + g;
          M[i][j] = BIG_NUM;
          for (k = i; k <= j - 1; k++)
              if ((tmp = M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]) < M[i][j]){
                  M[i][j] = tmp;
                  P[i][j] = k;
              }
      }

• Time complexity

  • n + (n-1) \cdot 1 + (n-2) \cdot 2 + ... + (n-(n-1))\cdot (n-1) \\= n + \Sigma_{g=1}^{n-1}{(n-g)g} \\= O(n^3)

• Chained matrix multiplication problem

  • O(n^3) by Godbole (1973)
  • O(n^2) by Yao (1972)
  • O(n log n) by Hu and Shing (1982, 1984)

  j/ i	1	2	3	4	5	6	7	8
  1	0
  2		0
  3			0
  4				0
  5					0
  6						0
  7							0
  8								0

• Printing optimal order

  • M(2,7) = \min_{2\leq k \leq 6}{\{ M(2,k) + M(k+1,7)+d_1 d_k d_7}\}
  

  void order(int i, int j)
  {
      int k;
      if (i == j)
          printf(“A_ % d”, i);
      else
      {
          k = P[i][j];
          printf(“(“);
                order(i, k); order(k + 1, j); printf(“)”);
      }
  }

→ O(n) time