Unit 4: Dynamic Programming

I. Orientation — Principle of Dynamic Programming

Dynamic programming (DP), developed systematically by Richard Bellman in the 1950s, is an algorithm-design method for problems whose optimal solutions can be constructed from optimal solutions to smaller, repeated subproblems. It replaces repeated computation with stored results and is especially useful in optimization, counting, and decision problems.

• Principle of optimality: An optimal solution contains optimal solutions to its relevant subproblems. If an optimal route from vertex (s) to vertex (t) passes through (v), then its portion from (s) to (v) must also be optimal under the same criteria.
• Optimal substructure: The value of a problem can be expressed using optimal values of smaller instances, as in (F(i)=\min_j{c(i,j)+F(j)}).
• Overlapping subproblems: The same smaller instances recur. For example, a naive recursive Fibonacci computation evaluates (F(3)) multiple times.
• State: A state records all information needed to describe a subproblem; examples include an index (i), an interval ((i,j)), or a capacity (w).
• Decision: Each state considers one or more choices, such as a split position (k) in matrix-chain multiplication.
• Recurrence: A mathematical relation connects each state to smaller states and specifies whether their values are minimized, maximized, or combined.
• Base cases: Smallest subproblems have directly known values, such as a single matrix requiring zero multiplication cost.
• Storage convention: Results are kept in a table or map so that each distinct state is solved once.
• Reconstruction: A second table may retain the decision made at each state, allowing the optimal solution—not merely its value—to be recovered.
• Complexity basis: DP time is generally the number of states multiplied by the work per state; space is determined by the number of stored states.

II. General Method — Designing a Dynamic Programming Solution

A. General method

The general method is to identify reusable subproblems, formulate a recurrence, compute every required state once, and reconstruct the resulting solution when necessary.

• Step 1—characterize the solution: Determine how an optimal solution can be decomposed. For an interval ((i,j)), a common characterization is that the final solution makes some decision (k) and combines solutions to ((i,k)) and ((k+1,j)).
• Step 2—define the state precisely: Assign one meaning to each table entry. If (D[i]) denotes the minimum cost for the first (i) objects, this meaning must remain unchanged throughout the recurrence and implementation.
• Step 3—derive the recurrence: Express the state value using smaller states:
  
  TEXT

    D[i] = min { D[j] + cost(j, i) : 0 ≤ j < i }

  
  Here, (D[i]) is the optimal cost for the first (i) items, (j) is the previous boundary, and (\operatorname{cost}(j,i)) is the cost of choosing items (j+1) through (i) as the final component.
• Step 4—specify base and impossible states: Set directly solvable states such as (D[0]=0). A minimization state that is initially unreachable is commonly assigned (+\infty), preventing it from being selected accidentally.
• Step 5—choose an evaluation strategy:
  1. Top-down memoization: Begin with the original problem, recursively request smaller states, and cache each result. It naturally avoids states that are never reached but uses recursion-stack space.
  2. Bottom-up tabulation: Evaluate states in dependency order, usually from smaller sizes to larger sizes. It avoids recursive overhead and makes time and space usage explicit.
• Step 6—record decisions: If the actual optimal arrangement is needed, store an argument such as
  (\operatorname{choice}[i]=\arg\min_j(D[j]+\operatorname{cost}(j,i))). Following these choices backward reconstructs the arrangement.
• Bottom-up pattern: A generic minimization implementation is:
  
  TEXT

    D[0] ← 0
    for i ← 1 to n:
        D[i] ← +∞
        for each valid predecessor j of i:
            candidate ← D[j] + cost(j, i)
            if candidate < D[i]:
                D[i] ← candidate
                choice[i] ← j
    return D[n]

  
  Here, (n) is the input size, (D) is the value table, and choice records optimal predecessors.
• Correctness argument: Prove by induction over the evaluation order. The base states are correct directly; for state (i), assume every required smaller state is optimal, then show that the recurrence examines every valid final decision and selects the best one.
• Complexity analysis: If there are (S) states and at most (T) transitions per state, the running time is (O(ST)). Storing one value and one decision per state requires (O(S)) space.
• Applicability boundary: Dynamic programming is unsuitable when states omit information needed by later decisions or when optimal substructure fails. It may also be impractical when the state space is exponential, even though repeated recursion has been removed.

III. Chained Matrix Multiplication — Choosing an Optimal Parenthesization

A. Chained matrix multiplication

Chained matrix multiplication determines how to parenthesize a compatible sequence of matrices so that the number of scalar multiplications is minimized; it does not alter the matrices’ order.

• Dimension model: For matrices (A_1,A_2,\ldots,A_n), let (Ai) have dimensions (p{i-1}\times p_i). The product is compatible because the column count (p_i) of (Ai) equals the row count of (A{i+1}).
• Cost rule: Multiplying an (a\times b) matrix by a (b\times c) matrix requires (abc) scalar multiplications under the standard algorithm.
• Why order matters: Matrix multiplication is associative, so ((A_1A_2)A_3=A_1(A_2A_3)), but the two parenthesizations can have different costs. Matrix multiplication is not commutative, so matrix order cannot be rearranged.
• State definition: Let (m[i,j]) be the minimum scalar-multiplication cost for (AiA{i+1}\cdots A_j). A single matrix needs no multiplication, giving (m[i,i]=0).
• Recurrence: If the final multiplication splits after (Ak), the left and right products cost (m[i,k]) and (m[k+1,j]), while combining them costs (p{i-1}p_kp_j):
  
  TEXT

    m[i,j] = min {
        m[i,k] + m[k+1,j] + p[i−1]·p[k]·p[j]
        : i ≤ k < j
    }

  
  Here, (i) and (j) are chain endpoints, (k) is the final split, and (p_r) is the corresponding dimension value.
• Evaluation order: Since (m[i,j]) depends on shorter intervals, compute chains by increasing length (L=2,3,\ldots,n):
  
  TEXT

    for i ← 1 to n:
        m[i,i] ← 0
    for L ← 2 to n:
        for i ← 1 to n−L+1:
            j ← i+L−1
            m[i,j] ← +∞
            for k ← i to j−1:
                q ← m[i,k] + m[k+1,j] + p[i−1]·p[k]·p[j]
                if q < m[i,j]:
                    m[i,j] ← q
                    s[i,j] ← k

  
  The table (s[i,j]) stores the optimal split.
• Worked example: Let (A_1) be (10\times30), (A_2) be (30\times5), and (A_3) be (5\times60).
  • ((A_1A_2)A_3) costs (10\cdot30\cdot5+10\cdot5\cdot60=4{,}500).
  • (A_1(A_2A_3)) costs (30\cdot5\cdot60+10\cdot30\cdot60=27{,}000).
  • Therefore, ((A_1A_2)A_3) saves (22{,}500) scalar multiplications.
• Complexity: There are (O(n^2)) intervals and up to (O(n)) split positions per interval, producing (O(n^3)) time. Tables (m) and (s) each occupy (O(n^2)) space.

B. Applications and limitations

The algorithm is valuable whenever an associative sequence operation has parenthesization-dependent cost, but its classical cost model does not capture every practical concern.

• Applications: Database query optimization, compiler expression planning, tensor contraction, and scientific-computing pipelines use similar interval recurrences.
• Solution reconstruction: Recursively split ((i,j)) at (s[i,j]); print (A_i) when (i=j), otherwise reconstruct ((i,s[i,j])) and ((s[i,j]+1,j)).
• Model limitation: Scalar-operation count ignores memory hierarchy, parallel execution, sparsity, and numerical-library behavior; the theoretically cheapest parenthesization may not have the shortest wall-clock time.

IV. Optimal Storage on Tapes — Minimizing Mean Retrieval Time

A. Optimal storage on tapes

Optimal storage on tapes arranges files on sequential-access media so that expected retrieval time is minimized, because accessing a file requires scanning all files placed before it.

• Model: For (n) files, let file (i) have length (L_i>0) and access probability (Pi\ge 0), with (\sum{i=1}^{n}P_i=1). For an order (\pi), the retrieval time of the file at position (j) is:
  
  TEXT

    Tπ(j) = Σ(k=1 to j) Lπ(k)

  
  Here, (\pi(k)) identifies the file in position (k).
• Objective: The mean retrieval time (MRT) is:
  
  TEXT

    MRT(π) = Σ(j=1 to n) Pπ(j) · Tπ(j)

  
  Each file’s completion position is weighted by its probability of retrieval.
• Equal-probability rule: If every file is requested equally often, arrange files by nondecreasing length. A shorter file placed earlier reduces its own retrieval time and the retrieval times of all subsequent files.
• Unequal-probability rule: Arrange files by nondecreasing ratio (L_i/P_i), equivalently by nonincreasing (P_i/L_i). A file with (P_i=0) is placed last because its ratio is treated as infinite.
• Exchange justification: Consider adjacent files (a) and (b). Ordering (a,b) contributes (P_aL_a+P_b(L_a+L_b)); ordering (b,a) contributes (P_bL_b+P_a(L_b+L_a)). The first is no worse precisely when:
  
  TEXT

    L[a] / P[a] ≤ L[b] / P[b]

  
  Thus, any ratio inversion can be exchanged without increasing MRT, proving the sorted order is optimal.
• Worked example: Suppose files have ((L_i,P_i)) values (A=(20,0.5)), (B=(10,0.2)), and (C=(30,0.3)). Their ratios are (40), (50), and (100), so the order is (A,B,C). Retrieval times are (20), (30), and (60), yielding:
  
  TEXT

    MRT = 0.5(20) + 0.2(30) + 0.3(60) = 34 length-units

• Algorithmic cost: Computing ratios takes (O(n)); comparison sorting takes (O(n\log n)); evaluating MRT after sorting takes (O(n)).

B. Applications and limitations

The tape-storage rule models ordered sequential access clearly, but it depends on stable lengths, known request probabilities, and a single linear storage sequence.

• Applications: The same objective appears in single-machine scheduling, where minimizing weighted completion time orders jobs by processing-time-to-weight ratio (L_i/P_i).
• Multiple tapes: With several tapes, files must be assigned to tapes as well as ordered, introducing a partitioning decision; dynamic programming may be used when tape capacities or assignment constraints are present.
• Limitations: Random-access storage, changing access frequencies, file replication, compression, and rewind costs require modified states and objective functions rather than the basic ratio rule.