Dynamic programming notes — Unit 4

Divide and Conquer solves problems by splitting them into completely independent subproblems. But what happens if the subproblems are NOT independent? What if the recursion tree forces you to solve the exact same mathematical problem hundreds of times?

⇒1.1 The Fibonacci Disaster

Consider the naive recursive function for the Fibonacci sequence: `fib(n) = fib(n-1) + fib(n-2)`.

If you call `fib(5)`, it calls `fib(4)` and `fib(3)`.
The `fib(4)` call then recursively calls `fib(3)` again.
The execution tree grows exponentially. To calculate `fib(50)`, the CPU will literally compute the answer to `fib(2)` over a trillion times. The time complexity is $O(2^n)$.

Dynamic Programming (DP) is a paradigm designed specifically to cure this exact disease.

Dynamic Programming solves optimization problems by breaking them down into simpler subproblems, solving each subproblem exactly once, and storing their solutions in a memory structure (like an array or matrix).

If the algorithm needs the answer to a subproblem again, it simply looks it up in the table instead of recalculating it. It trades Space (using RAM to store tables) for a massive increase in Speed (dropping complexity from Exponential to Polynomial).

⇒2.1 Required Properties

A problem can ONLY be solved using DP if it possesses two mathematical properties:

• Overlapping Subproblems: The recursive solution must revisit the exact same problem over and over again (like the Fibonacci example).
• Optimal Substructure: The optimal, perfect solution to the massive, overarching problem can be constructed directly from the optimal, perfect solutions of its smaller subproblems.

There are two distinct ways to write a Dynamic Programming algorithm.

⇒3.1 Top-Down (Memoization)

You write a standard, natural recursive function. However, before the function does any math, it checks a global lookup table (memo).
- If the answer is in the table, return it instantly.
- If not, do the expensive recursive calculation, save the answer in the table, and then return it.

⇒3.2 Bottom-Up (Tabulation)

You completely abandon recursion. You build an iterative algorithm using `for` loops. You start by calculating the absolute smallest base cases (e.g., `fib(0)` and `fib(1)`), store them in an array, and iteratively build up the table until you reach the final answer (`fib(n)`).

Engineering Note: Bottom-Up Tabulation is generally preferred because it has absolutely zero overhead from recursive function calls and prevents Stack Overflow errors.

Given a sequence of matrices $(A_1 \times A_2 \times A_3 \times A_4)$, we need to multiply them together.

Matrix multiplication is associative. We can parenthesize this equation in many ways: $(A_1(A_2(A_3A_4)))$ or $((A_1A_2)(A_3A_4))$. The final mathematical answer is identical.

⇒4.1 The Optimization Problem

Multiplying a $(p \times q)$ matrix by a $(q \times r)$ matrix requires $p \times q \times r$ scalar multiplications.

Because matrices have varying dimensions, the specific order in which we place the parentheses drastically alters the total number of arithmetic operations required. A bad parenthesis placement might take 100,000 operations, while the optimal placement might take only 5,000.

Goal: Find the optimal parenthesization that strictly minimizes the total number of scalar multiplications.

We cannot use a Greedy approach here because making a cheap local multiplication might force us into an astronomically expensive multiplication later.

⇒5.1 The Recurrence

Let $m[i, j]$ be the absolute minimum cost to multiply the chain of matrices from $A_i$ to $A_j$.

To find the optimal cost for the whole chain $A_1...A_n$, we must try splitting the chain at every possible internal point $k$.

$m[i, j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \le k < j} \{ m[i,k] + m[k+1,j] + p_{i-1}p_kp_j \} & \text{if } i < j \end{cases}$

The DP algorithm builds a 2D table bottom-up, starting with chains of length 1, then length 2, up to length $n$.

Time Complexity: The algorithm requires three nested loops to fill the 2D table. Therefore, it takes $O(n^3)$ time.

A fundamental problem in DNA sequence analysis (bioinformatics) and version control systems (`git diff`).

Given two sequences, $X$ and $Y$, find the length of the longest sequence that appears in both $X$ and $Y$ in the same relative order. (Crucially, a subsequence does not need to be contiguous; characters can be skipped).

Example:
$X$ = `ABCBDAB`
$Y$ = `BDCABA`
The LCS is `BCBA` (length 4).

⇒6.1 The Brute Force Failure

A sequence of length $m$ has $2^m$ possible subsequences. Generating all of them and checking against $Y$ takes exponential time, $O(n 2^m)$, which is impossible for strings longer than 40 characters.

We build a 2D table where `L[i][j]` represents the length of the LCS of the prefix $X[1..i]$ and the prefix $Y[1..j]$.

⇒7.1 The Recurrence

We compare the last characters of the prefixes.

• Match: If $X[i] == Y[j]$, then this character MUST be part of the LCS. We add 1 to the result of the remaining prefixes.
  `L[i][j] = 1 + L[i-1][j-1]`
• Mismatch: If $X[i] \neq Y[j]$, they cannot both be part of the LCS. We take the maximum of skipping a character from $X$ or skipping a character from $Y$.
  `L[i][j] = MAX( L[i-1][j] , L[i][j-1] )`

We fill a table of size $(m+1) \times (n+1)$ using a double loop.

Time Complexity: Filling every cell takes $O(1)$ time. There are $m \times n$ cells. Therefore, the total time is $O(mn)$.

Recall the Fractional Knapsack from Unit 3. We solved it efficiently using a Greedy algorithm based on value/weight ratio.

In the 0/1 Knapsack, the rules change: You cannot break items into fractions. You must either take the whole item (1) or leave it entirely (0).

⇒8.1 The Greedy Failure

The Greedy approach completely fails here. Picking an item with a huge value/weight ratio might consume 90% of the knapsack's capacity, preventing you from fitting two slightly less efficient items that together would yield a much higher total profit.

To solve 0/1 Knapsack perfectly, we must evaluate the cascading consequences of taking or leaving every single item, requiring Dynamic Programming.

We construct a 2D table `K[i][w]` which stores the maximum profit achievable using only the first `i` items, given a strict weight limit of `w`.

⇒9.1 The Logic

For every item $i$, we have a binary choice: take it or leave it.

• Leave it: The profit is the same as if item $i$ didn't exist.
  `Profit = K[i-1][w]`
• Take it: We gain the value of item $i$, but we lose its weight from our capacity.
  `Profit = Value[i] + K[i-1][w - Weight[i]]`

The recurrence simply takes the maximum of those two choices:

`K[i][w] = MAX( K[i-1][w], Value[i] + K[i-1][w - Weight[i]] )`

Time Complexity: The table has $n$ rows (items) and $W$ columns (capacity). Therefore, the complexity is $O(nW)$. (This is technically called pseudo-polynomial time).

Recall Dijkstra's Algorithm (Unit 3). It finds the shortest path, but critically fails if the graph contains negative edge weights.
The Bellman-Ford Algorithm uses a Dynamic Programming approach to solve the Single-Source Shortest Path problem, and it flawlessly handles negative edge weights.

⇒10.1 The Edge Relaxation Strategy

Instead of greedily picking the closest node, Bellman-Ford is brute-force robust. It systematically relaxes EVERY SINGLE EDGE in the entire graph. Then, it repeats that entire process $V-1$ times.

Why $V-1$ times? Because the longest possible path without cycles in a graph with $V$ vertices can contain at most $V-1$ edges. By relaxing all edges $V-1$ times, we mathematically guarantee that shortest path information has propagated across the entire graph.

The true power of Bellman-Ford lies in its ability to detect mathematically impossible scenarios.

⇒11.1 The Detection Mechanism

If a graph contains a Negative Weight Cycle, no shortest path can exist, because you can continuously loop through the negative cycle to achieve a path cost of negative infinity.

Bellman-Ford detects this brilliantly. After relaxing all edges $V-1$ times, the distance array is theoretically perfect. The algorithm then runs one final, extra pass (the $V^{th}$ time) over all edges.

If, during this final pass, ANY edge can still be relaxed (meaning a distance value decreases), it mathematically proves that a Negative Weight Cycle exists in the graph, and the algorithm reports a failure.

Time Complexity: Relaxing $E$ edges, repeated $V$ times. Total time is $O(VE)$. It is slower than Dijkstra, but handles negative weights.

Dijkstra and Bellman-Ford only find paths from ONE specific starting city to all other cities.
What if an airline company needs a massive table showing the shortest path from EVERY city to EVERY OTHER city simultaneously?

⇒12.1 The Naive Approach

We could just run Dijkstra's algorithm $V$ times (once from each vertex as the source). The time complexity would be $V imes O(V^2) = O(V^3)$.
However, this still completely fails if the graph has negative weights.

To solve the All-Pairs Shortest Path problem correctly for any graph, we use the Floyd-Warshall Algorithm, a pure Dynamic Programming masterpiece.

Floyd-Warshall uses an adjacency matrix `D` to store shortest distances.

⇒13.1 The DP Logic

Consider a path from vertex $i$ to vertex $j$. We check every other vertex $k$ in the graph to see if it can act as a useful intermediate stopping point.

For every pair $(i, j)$, and every possible intermediate vertex $k$, we ask the question:
"Is it shorter to go directly from $i$ to $j$, or is it shorter to go from $i$ to $k$, and then from $k$ to $j$?"

The Recurrence:
`D[i][j] = MIN( D[i][j], D[i][k] + D[k][j] )`

The algorithm consists of three incredibly simple nested loops:
```c
for (k = 0; k < V; k++)
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
D[i][j] = MIN(D[i][j], D[i][k] + D[k][j]);
```

Time Complexity: Due to the three nested loops, the complexity is strictly $O(V^3)$. It elegantly handles negative edges and is incredibly easy to implement in code.

Unit 4 deals with complex table-filling problems. Exam questions almost always require you to draw and fill out the DP matrices step-by-step.

⇒14.1 University Exam Checklist

• What are the two required properties of a problem for Dynamic Programming to be applicable?
• Explain the difference between Memoization (Top-Down) and Tabulation (Bottom-Up).
• Write the DP recurrence equation for Matrix Chain Multiplication.
• Given 4 matrices with specific dimensions, construct the MCM cost table and find the optimal parenthesization.
• Given two strings, construct the 2D DP table and trace back the Longest Common Subsequence (LCS).
• Explain why the Greedy algorithm fails for the 0/1 Knapsack problem, and write the DP recurrence relation that solves it.
• Execute the Bellman-Ford algorithm on a graph to find shortest paths. Explain how it detects Negative Weight Cycles.
• Execute the Floyd-Warshall algorithm. State its time complexity and write the three-line pseudo-code.