Unit 5: Dynamic Programming Problems

I. Dynamic Programming Foundations

Dynamic programming (DP) solves problems by expressing a solution through smaller, overlapping subproblems and storing their results. It is applicable when a problem has optimal substructure, meaning an optimal solution can be constructed from optimal solutions to smaller instances.

• State: A compact description of a subproblem, such as dp[i], representing an answer involving the first i elements.
• Recurrence: An equation connecting a state to smaller states; for example, dp[i] = min(dp[i-1], dp[i-2]) + cost[i].
• Base cases: Directly known answers that terminate the recurrence, such as dp[0] = 0.
• Memoization: A top-down method that recursively evaluates states and caches each result.
• Tabulation: A bottom-up method that evaluates states in dependency order.
• Correctness: Usually established by defining the state precisely, proving the recurrence covers every valid choice, and verifying the base cases.
• Complexity: Commonly calculated as number of states × work per state; memory can often be reduced when only recent states are needed.

II. Longest Increasing Subsequence

A. Longest increasing subsequence

The longest increasing subsequence problem finds the maximum-length subsequence whose values are strictly increasing.

• Subsequence: Elements retain their original order but need not be adjacent; [3, 5, 8] is a subsequence of [3, 1, 5, 2, 8].
• State definition: Let dp[i] be the LIS length ending exactly at index i.
• Recurrence: A previous element a[j] can precede a[i] only when j < i and a[j] < a[i].

dp[i] = 1 + max(dp[j]) for all j < i with a[j] < a[i]
dp[i] = 1 if no valid j exists
answer = max(dp[i])

Here, a[i] is the value at index i, and dp[i] is the best increasing-subsequence length ending there.

• Complexity: The direct DP checks every pair (j, i), requiring O(n²) time and O(n) space.
• Reconstruction: Store parent[i] = j whenever dp[j] + 1 improves dp[i], then trace backward from the maximum state.

B. Longest Increasing Subsequence (LIS)

LIS can also be computed in O(n log n) time by maintaining the smallest possible tail for each subsequence length.

• Tail invariant: tails[k] stores the minimum final value found for an increasing subsequence of length k + 1.
• Update rule: For each value x, binary-search the first position whose value is at least x and replace it with x; append x if no such position exists.
• Interpretation: Replacing a tail does not itself preserve the complete subsequence, but it improves the chance of extending a subsequence later.
• Strictness: lower_bound, the first value >= x, handles strictly increasing LIS; upper_bound, the first value > x, handles non-decreasing subsequences.
• Result: After processing all elements, len(tails) is the LIS length, with O(n) auxiliary space.

III. Longest Common Subsequence

A. Longest common subsequence

The longest common subsequence problem finds the greatest-length sequence occurring in two sequences in the same relative order.

• State definition: Let dp[i][j] be the LCS length of prefixes X[0...i-1] and Y[0...j-1].
• Base cases: dp[0][j] = 0 and dp[i][0] = 0, because an empty sequence has no non-empty common subsequence.
• Recurrence:

if X[i-1] == Y[j-1]:
    dp[i][j] = 1 + dp[i-1][j-1]
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Here, i and j are prefix lengths, while X and Y are the input sequences.

• Complexity: For lengths m and n, tabulation requires O(mn) time and O(mn) space.
• Reconstruction: From dp[m][n], move diagonally when characters match; otherwise move toward the neighboring state with the larger value.

B. Longest Common Subsequence (LCS)

LCS illustrates the difference between subsequences and substrings while supporting important space optimizations.

• Order requirement: Characters must appear in the same order, but gaps are allowed; "ace" is a subsequence of "abcde".
• Substring contrast: A substring must be contiguous, so its recurrence resets to zero after a mismatch; LCS instead takes the maximum of two prefix states.
• Space optimization: Each row depends only on the preceding row and the current row’s previous entry, reducing storage to O(min(m,n)).
• Limitation: Space optimization loses the complete decision table needed for straightforward reconstruction.
• Applications: LCS models file comparison, version differences, DNA sequence similarity, and minimum insertion/deletion transformations.

IV. Binomial Coefficient

A. Binomial coefficient

The binomial coefficient counts the ways to choose k objects from n distinct objects without regard to order.

• Definition:

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

Here, n is the number of available objects, k is the number selected, and ! denotes factorial.

• 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: Fill rows for i = 0...n, computing valid columns j = 0...min(i,k).
• Complexity: Restricting computation to the required columns gives O(nk) time and O(k) space.
• Update order: A one-dimensional table must be updated from k downward to prevent values from the current row overwriting dependencies.
• Numerical concern: Coefficients grow rapidly, so fixed-width integer overflow may require arbitrary-precision arithmetic or modular computation.

V. Box Stacking

A. Box Stacking

Box stacking maximizes stack height by choosing box orientations while requiring every upper base to be strictly smaller than the base below it.

• Orientation generation: A three-dimensional box can produce three orientations by selecting each dimension as height; normalize each base so its longer side is listed first.
• Ordering: Sort orientations by decreasing base area or another order consistent with considering larger bases before smaller ones.
• State definition: Let dp[i] be the maximum stack height with orientation i placed on top.
• Transition:

dp[i] = height[i] + max(dp[j])
where baseLength[j] > baseLength[i]
  and baseWidth[j] > baseWidth[i]

Here, j represents a valid lower orientation and i the orientation placed above it.

• Answer: The maximum value among all dp[i] states is the tallest stack.
• Complexity: With 3n orientations, pairwise transitions take O(n²) time and O(n) DP space.
• Model constraint: Whether rotations or repeated box types are permitted must match the problem statement; generated orientations alone do not settle duplication rules.

VI. Integer Knapsack

A. Integer Knapsack Problem (Duplicate Items Forbidden)

The duplicate-forbidden integer knapsack is the 0/1 knapsack problem, where each item is either selected once or omitted.

• Inputs: Item i has integer weight w[i], value v[i], and the knapsack has capacity W.
• State definition: dp[i][c] is the maximum value using the first i items with capacity c.
• Choice recurrence:

if w[i-1] <= c:
    dp[i][c] = max(dp[i-1][c],
                   v[i-1] + dp[i-1][c-w[i-1]])
else:
    dp[i][c] = dp[i-1][c]

Here, c is current capacity; both choices reference row i-1, ensuring item i-1 cannot be duplicated.

• Complexity: The table requires O(nW) time and O(nW) space, where n is the item count.
• Space optimization: Use dp[c] and process capacities from W down to w[i], producing O(W) space.
• Critical contrast:
  1. 0/1 knapsack: Descending capacity order forbids reuse.
  2. Unbounded knapsack: Ascending capacity order permits repeated use of the current item.
• Classification: O(nW) is pseudo-polynomial because it depends on the numeric capacity rather than the number of bits encoding W.

VII. Edit Distance

A. Edit Distance

Edit distance measures the minimum number of permitted operations needed to transform one string into another.

• Operations: Standard Levenshtein distance allows insertion, deletion, and substitution, each with cost 1.
• State definition: dp[i][j] is the minimum cost to convert the first i characters of string A into the first j characters of string B.
• Base cases: dp[i][0] = i deletions and dp[0][j] = j insertions.
• Recurrence:

if A[i-1] == B[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],    deletion
        dp[i][j-1],    insertion
        dp[i-1][j-1]   substitution
    )

• Complexity: Strings of lengths m and n require O(mn) time and O(mn) space, reducible to O(min(m,n)) space.
• Weighted variant: Replace the constant 1 with operation-specific costs when insertions, deletions, and substitutions are not equally expensive.
• Applications: Spell correction, approximate search, record matching, and biological sequence comparison use edit-distance models.

VIII. Matrix Chain Multiplication

A. Matrix Chain Multiplication

Matrix chain multiplication chooses a parenthesization that minimizes scalar multiplications without changing matrix order.

• Dimension representation: If matrix A_i has dimensions p[i-1] × p[i], then a chain of n matrices uses an array p of length n + 1.
• State definition: dp[i][j] is the minimum multiplication cost for matrices A_i through A_j.
• Base case: dp[i][i] = 0, because one matrix requires no multiplication.
• Recurrence:

dp[i][j] = min over i <= k < j of
           dp[i][k] + dp[k+1][j]
           + p[i-1] * p[k] * p[j]

Here, k is the final split point, and the product term is the cost of multiplying the two resulting matrices.

• Evaluation order: Compute chains by increasing length, beginning with length 2.
• Complexity: There are O(n²) intervals and up to O(n) splits per interval, giving O(n³) time and O(n²) space.
• Reconstruction: Store the minimizing split k for each interval, then recursively print the corresponding parenthesization.
• Scope: DP changes the operation order and cost, not the mathematical product.

IX. Balanced Partition

A. Balanced Partition

Balanced partition divides a set into two subsets so that the absolute difference between their sums is minimized.

• Total-sum relation: If the total is S and one subset has sum x, the other has sum S-x; the difference is |S-2x|.
• Reduction: Find the largest reachable subset sum x <= floor(S/2).
• Boolean state: dp[s] is true when some subset of processed elements has sum s.
• Transition:

dp[0] = true
for each value x:
    for s from floor(S/2) down to x:
        dp[s] = dp[s] or dp[s-x]

Here, descending s ensures each input value x is used at most once.

• Answer: If best is the largest reachable sum at most S/2, the minimum difference is S - 2*best.
• Complexity: For n values and total sum S, the method requires O(nS) time and O(S) space.
• Assumption: This standard formulation expects non-negative integers; negative numbers require shifted indices or a set-based state representation.

B. Balanced Partition Problem

The balanced partition problem is a subset-sum optimization whose exact-equality case can be identified from the same DP table.

• Exact balance: A difference of zero is possible only when S is even and subset sum S/2 is reachable.
• Decision versus optimization:
  1. Decision form: Determine whether two equal-sum subsets exist.
  2. Optimization form: Find the smallest possible difference when equality is impossible.
• Reconstruction: Store predecessor decisions or retain a two-dimensional table, then trace selected values contributing to best.
• Pseudo-polynomial behavior: Runtime is polynomial in S, but not in the bit-length of the input values.
• Practical alternative: When n is small but values are large, meet-in-the-middle subset enumeration can replace sum-indexed DP, typically using about O(2^(n/2)) time and space.