Unit 3: Dynamic Programming

I. Foundations of Dynamic Programming

A. Introduction to Dynamic Programming

Dynamic programming (DP), developed systematically by Richard Bellman in the 1950s, solves a complex problem by combining stored solutions to smaller, recurring subproblems.

• Governing principle: DP is applicable when a problem exhibits:
  • Optimal substructure: An optimal solution can be constructed from optimal solutions of smaller subproblems.
  • Overlapping subproblems: The same subproblems recur, so storing their answers avoids repeated computation.
• State: A state records the information needed to identify a subproblem; for example, DP[i][w] may denote the best knapsack value using the first (i) items and capacity (w).
• Recurrence: A recurrence expresses each state in terms of smaller states:

solution(state) = best combination of solutions(smaller states)

• Base cases: These are the smallest directly solvable states, such as (C(n,0)=1) for binomial coefficients.
• Evaluation methods:
  1. Top-down memoization: Recursively evaluates only required states and caches each result.
  2. Bottom-up tabulation: Iteratively evaluates states in an order that guarantees all dependencies are already available.
• Solution design:
  • Define the state precisely.
  • Derive the recurrence.
  • specify base cases.
  • Select a valid evaluation order.
  • Store decisions if the actual solution, rather than only its value, must be recovered.
• Complexity principle: Runtime is approximately the number of distinct states multiplied by the work per state. Memory can sometimes be reduced by retaining only the previous row, column, or diagonal.
• Limitation: DP may require excessive space when the state contains several large dimensions; for example, knapsack takes (O(nW)) time, which is impractical when capacity (W) is numerically large.

II. Computing a Binomial Coefficient

A. Computing a Binomial Coefficient

A binomial coefficient (\binom{n}{k}) counts the ways to select (k) objects from (n) distinct objects without regard to order.

• Direct definition: For integers (0\leq k\leq n),

C(n, k) = n! / (k!(n-k)!)

Here, (n!) is the factorial of (n), and (C(n,k)=\binom{n}{k}).

• DP recurrence: Pascal’s identity divides selections according to whether a designated object is excluded or included:

C(n, k) = C(n-1, k) + C(n-1, k-1)
C(n, 0) = C(n, n) = 1

• Tabulation algorithm:

BINOMIAL(n, k):
    create C[0..n][0..k]
    for i = 0 to n:
        for j = 0 to min(i, k):
            if j = 0 or j = i:
                C[i][j] = 1
            else:
                C[i][j] = C[i-1][j-1] + C[i-1][j]
    return C[n][k]

• Worked example: Using Pascal’s identity,

C(5, 2) = C(4, 1) + C(4, 2) = 4 + 6 = 10

• Complexity: The table uses (O(nk)) time and (O(nk)) space. Space becomes (O(k)) by updating a one-dimensional array from right to left, preventing overwritten values from being reused prematurely.
• Practical advantage: Unlike factorial evaluation, the recurrence can avoid computing very large intermediate factorials and can generate an entire row of Pascal’s triangle.

III. Top-Down Dynamic Programming

A. Memory Functions

A memory function is a top-down dynamic-programming method that combines recursion with a table storing previously computed subproblem values.

• Operating rule: On receiving a state, the function first checks the table; it computes the state recursively only if no stored value exists.
• Generic structure:

F(state):
    if state is a base case:
        return base value
    if memo[state] is defined:
        return memo[state]
    memo[state] = combine(F(smaller states))
    return memo[state]

• Contrast:
  1. Ordinary recursion: Recomputes recurring states; naive Fibonacci evaluation has exponential time because calls such as (F(n-2)) appear in several branches.
  2. Memory function: Computes each distinct state once; memoized Fibonacci evaluation takes (O(n)) time and (O(n)) storage.
• Demand-driven evaluation: Only states reachable from the original problem are evaluated, which can save work when many entries of a full DP table are irrelevant.
• Cost: A lookup and recursive-call overhead accompany each state, while recursion may consume stack space proportional to the longest dependency chain.
• Correctness requirement: A special marker such as UNDEFINED must be distinguished from valid results, including zero or negative values.

IV. Resource Allocation

A. Knapsack Problem

The 0/1 knapsack problem selects indivisible items to maximize total value without exceeding a fixed capacity.

• Input: There are (n) items; item (i) has weight (w_i), value (v_i), and capacity is (W). Each item is either selected once or excluded.
• State definition: (K[i,w]) is the maximum value obtainable from the first (i) items with capacity (w).
• Recurrence:

K[i, w] = K[i-1, w]                         if w_i > w
K[i, w] = max(K[i-1, w],
              v_i + K[i-1, w-w_i])          if w_i ≤ w
K[0, w] = 0 and K[i, 0] = 0

• Decision meaning: The first candidate excludes item (i); the second includes it and adds its value to the best solution for the remaining capacity.
• Worked example: For items ((w,v)=(2,3),(3,4),(4,5)) and (W=5), selecting weights (2) and (3) gives value (7), exceeding either feasible single item.
• Reconstruction: Starting at (K[n,W]), if (K[i,w]\neq K[i-1,w]), item (i) was included; then replace (w) by (w-w_i).
• Complexity: Tabulation requires (O(nW)) time and (O(nW)) space. A descending-capacity one-dimensional update reduces space to (O(W)).
• Important distinction: Descending updates enforce 0/1 selection; ascending updates allow an item to be reused and therefore solve the unbounded knapsack variant.
• Limitation: (O(nW)) is pseudo-polynomial because it depends on numeric capacity (W), not merely on the number of bits used to represent (W).

V. Optimal Parenthesization

A. Matrix-Chain Multiplication

Matrix-chain multiplication finds the parenthesization that minimizes scalar multiplications while preserving the fixed order of matrices.

• Dimension model: If matrix (Ai) has dimensions (p{i-1}\times p_i), multiplying an (a\times b) matrix by a (b\times c) matrix costs (abc) scalar multiplications.
• State definition: (m[i,j]) is the minimum cost of computing (AiA{i+1}\cdots A_j).
• Recurrence:

m[i, i] = 0

m[i, j] = min over i ≤ k < j of
           {m[i, k] + m[k+1, j] + p[i-1]p[k]p[j]}

The index (k) identifies the final split between (Ak) and (A{k+1}).

• Evaluation order: Chains are processed by increasing length, beginning with length (2), because each entry depends on shorter chains.
• Worked example: For dimensions (10\times30), (30\times5), and (5\times60):
  • ((A_1A_2)A_3) costs (10(30)(5)+10(5)(60)=4{,}500).
  • (A_1(A_2A_3)) costs (30(5)(60)+10(30)(60)=27{,}000).
  • Therefore, the first parenthesization is optimal.
• Reconstruction: Store the minimizing split in (s[i,j]), then recursively print the left chain (i\ldots s[i,j]) and right chain (s[i,j]+1\ldots j).
• Complexity: There are (O(n^2)) intervals and up to (O(n)) split points per interval, giving (O(n^3)) time and (O(n^2)) space.
• Scope: DP changes only the multiplication order, not the order of matrices, because matrix multiplication is associative but generally not commutative.

VI. Sequence Comparison

A. Longest Common Subsequence

The longest common subsequence problem finds the longest sequence appearing in two sequences in the same relative order, though not necessarily contiguously.

• Terminology: A subsequence deletes zero or more elements without rearranging the remainder; unlike a substring, its elements need not be adjacent.
• State definition: For sequences (X=x_1\ldots x_m) and (Y=y_1\ldots y_n), (L[i,j]) is the LCS length of prefixes (X[1..i]) and (Y[1..j]).
• Recurrence:

L[i, 0] = L[0, j] = 0

L[i, j] = 1 + L[i-1, j-1]                  if x_i = y_j
L[i, j] = max(L[i-1, j], L[i, j-1])        if x_i ≠ y_j

• Worked example: For X = ABCD and Y = AEBD, the sequence ABD appears in both in order, so the LCS length is (3).
• Reconstruction: Trace backward from (L[m,n]). Matching symbols enter the LCS and move diagonally; otherwise move toward a neighboring cell with the larger value.
• Complexity: The standard table takes (O(mn)) time and (O(mn)) space. If only the length is required, two rows reduce storage to (O(\min(m,n))).
• Non-uniqueness: Equal neighboring values may lead to different valid LCSs of the same maximum length.
• Applications: LCS supports file-difference tools, version comparison, DNA sequence analysis, and similarity measurement.

VII. Search Structures

A. Optimal Binary Search Trees

An optimal binary search tree arranges ordered keys to minimize expected search cost when access probabilities are known.

• Input model: Keys satisfy (k_1<k_2<\cdots<k_n); (p_i) is the probability of successfully finding (k_i), while (q_i) is the probability of an unsuccessful search between adjacent keys.
• State definitions:
  • (e[i,j]): Minimum expected cost for keys (k_i) through (k_j).
  • (w[i,j]): Total probability associated with that subtree.
• Base cases and recurrence:

e[i, i-1] = q[i-1]
w[i, i-1] = q[i-1]

w[i, j] = w[i, j-1] + p[j] + q[j]

e[i, j] = min over i ≤ r ≤ j of
          {e[i, r-1] + e[r+1, j] + w[i, j]}

Here, (r) is the candidate root; adding (w[i,j]) accounts for every subtree search moving one level deeper.

• Construction: Store the minimizing root in root[i][j]; recursively construct the left interval (i\ldots r-1) and right interval (r+1\ldots j).
• Evaluation order: Compute empty intervals first, followed by intervals of increasing key count.
• Complexity: The standard method tests (O(n)) roots for each of (O(n^2)) intervals, requiring (O(n^3)) time and (O(n^2)) space.
• Significance: Unlike a height-minimizing balanced tree, an optimal BST places frequently accessed keys nearer the root, minimizing weighted rather than worst-case search cost.
• Limitation: The resulting tree is optimal only for the supplied probability distribution; changing access frequencies may require rebuilding it.