Matrix Chain Multiplication & Optimization Problems

Matrix multiplication is associative: (A_1 A_2) A_3 = A_1 (A_2 A_3). However, the order of parenthesization dramatically impacts the number of scalar multiplications.

For a chain of n matrices where matrix A_i has dimension p_{i-1} times p_i:

Let m[i, j] be the minimum number of scalar multiplications needed to compute the product A_i .. A_j.

The Recurrence:

m[i, j] = 0 if i = j

m[i, j] = min_{i <= k < j} { m[i, k] + m[k+1, j] + p_{i-1} p_k p_j } if i < j.

Because computing m[i, j] requires values of smaller chain lengths, the table is filled diagonally by chain length l = 2, 3, ..., n.

Complexity: Theta(n^3) time and Theta(n^2) space.

Dynamic Programming on DAGs:

Because a Directed Acyclic Graph has no cycles, vertices can be linearized into a topological sort v_1, v_2, ..., v_n.

For longest path in a DAG:

dist[v] = max_{(u, v) in E} { dist[u] + w(u, v) }.

Evaluating in topological order ensures every subproblem dist[u] is finalized before computing dist[v]. Running time: O(V + E). Works with negative edge weights!

Held-Karp TSP Algorithm:

Brute force TSP checks (n - 1)! tours. Using DP:

Let C(S, j) be the minimum cost of visiting every vertex in subset S exactly once, starting at vertex 1 and ending at vertex j in S.

C(S, j) = min_{i in S setminus {j}} { C(S setminus {j}, i) + dist(i, j) }.

Time complexity: O(n^2 2^n), space O(n 2^n).