Dynamic Programming

Dynamic programming works when two conditions are met: (1) Optimal substructure — the optimal solution to the big problem contains optimal solutions to its subproblems (for example, the shortest path from A to C through B must include the shortest path from A to B). (2) Overlapping subproblems — when you break the problem down recursively, the same subproblems appear over and over (unlike divide-and-conquer, where subproblems are independent). When both conditions hold, DP avoids redundant work by storing subproblem results. There are two ways to implement DP: memoization (top-down) starts with the full problem, recursively breaks it down, and caches results so each subproblem is solved only once. Tabulation (bottom-up) fills in a table starting from the smallest subproblems, building up to the answer. Both achieve the same result but have different practical trade-offs.

Imagine you are a thief with a backpack (knapsack) that can hold at most W kilograms. There are n items in a room, each with a specific weight and value. You want to maximize the total value of items you take without exceeding the weight limit. The catch: for each item, you either take it entirely or leave it — no cutting items in half (that is why it is called '0/1'). The naive approach would try all 2^n possible combinations, which is exponentially slow. DP solves this efficiently by building a table: dp[i][w] represents the maximum value achievable using the first i items with a weight limit of w. For each item, you have two choices: skip it (dp[i][w] = dp[i-1][w]) or take it (dp[i][w] = value[i] + dp[i-1][w - weight[i]]). You pick whichever gives more value. This fills an (n+1) x (W+1) table in O(n*W) time.

Given two sequences (like two strings or two DNA strands), the LCS problem asks: what is the longest sequence of characters that appears in both, in the same order, but not necessarily consecutively? For example, the LCS of 'ABCBDAB' and 'BDCAB' is 'BCAB' (length 4). Note that a subsequence is different from a substring — characters do not need to be adjacent, they just need to maintain their relative order. The DP approach builds a 2D table where dp[i][j] represents the LCS length of the first i characters of string X and the first j characters of string Y. If X[i] matches Y[j], we extend the previous LCS by 1 (dp[i][j] = dp[i-1][j-1] + 1). If they do not match, we take the better of skipping either character (dp[i][j] = max(dp[i-1][j], dp[i][j-1])). This runs in O(m·n) time where m and n are the string lengths.

When multiplying a chain of matrices $A_1 \times A_2 \times \cdots \times A_n$, the order of multiplications (parenthesization) does not change the result but dramatically affects the number of scalar multiplications needed. For example, multiplying three matrices $A_1(10 \times 30)$, $A_2(30 \times 5)$, $A_3(5 \times 60)$ can be done as:

• -$((A_1 A_2) A_3)$: $10 \times 30 \times 5 + 10 \times 5 \times 60 = 1500 + 3000 =$ 4,500 multiplications
• -$(A_1 (A_2 A_3))$: $30 \times 5 \times 60 + 10 \times 30 \times 60 = 9000 + 18000 =$ 27,000 multiplications

That is a 6x difference! With more matrices, the gap grows even larger. The DP approach finds the optimal parenthesization.

Let $dp[i][j]$ = minimum cost to multiply matrices $A_i$ through $A_j$. We try every possible split point $k$ between $i$ and $j$: multiply $A_i \ldots A_k$ and $A_{k+1} \ldots A_j$ separately, then multiply the two results together. The cost of the final multiplication is $p_{i-1} \times p_k \times p_j$ (where the dimensions are stored in array $p$).

Worked example — dimensions $p = [10, 30, 5, 60]$:

• -$dp[1][2] = p_0 \cdot p_1 \cdot p_2 = 10 \cdot 30 \cdot 5 = 1500$
• -$dp[2][3] = p_1 \cdot p_2 \cdot p_3 = 30 \cdot 5 \cdot 60 = 9000$
• -$dp[1][3] = \min(dp[1][1] + dp[2][3] + 10 \cdot 30 \cdot 60,\; dp[1][2] + dp[3][3] + 10 \cdot 5 \cdot 60) = \min(0 + 9000 + 18000,\; 1500 + 0 + 3000) = \min(27000, 4500) =$ 4500