Chapter 6: Dynamic Programming

This paragraph introduces dynamic programming (DP) and linear programming as powerful, general-purpose problem-solving techniques. It contrasts them with more specialized methods like greedy algorithms or divide-and-conquer, which are elegant but only work for specific problem structures. Dynamic programming is presented as a "sledgehammer"—a versatile and powerful tool that can solve a very wide range of problems, especially when other methods fail.

This paragraph sets the stage by revisiting a problem that is easy to solve: finding the shortest path in a Directed Acyclic Graph (DAG). The text highlights that the solution to this specific problem contains the core logic that defines the entire paradigm of dynamic programming.

The key feature of a DAG that makes it easy to work with is that it has no cycles. This means its vertices can be linearized (also known as being topologically sorted)—arranged in a straight line such that all directed edges only point from left to right. This ordering is fundamental because it guarantees that by the time you process any node, you have already processed all the nodes that could possibly lead to it.

This section provides the core mathematical relationship, or recurrence relation, for this problem. The shortest path to any node D must pass through one of its immediate predecessors (B or C in the example). Therefore, we only need to compare the path lengths of those incoming routes:

• Path through B: dist(B) + length(B, D)
• Path through C: dist(C) + length(C, D)

We take the minimum of these options. Because we process the nodes in their linearized order, we are guaranteed to have already calculated the final values for dist(B) and dist(C) by the time we get to D.

                \begin{algorithm}
                    \caption{Shortest paths in a dag.}
                    \begin{algorithmic}
                        \State initialize all $dist(\cdot)$ values to $\infty$
                        \State $dist(s) \gets 0$
                        \For{each $v \in V \setminus \{s\}$, in linearized order}
                            \State $dist(v) \gets \min_{(u,v) \in E} \{dist(u) + l(u,v)\}$
                        \EndFor
                    \end{algorithmic}
                \end{algorithm}
                

This pseudocode shows the complete algorithm. It works in a single pass through the topologically sorted vertices:

1. Initialize all distances to infinity, except for the start node s, which is 0.
2. Go through the vertices one by one according to their linearized order.
3. For each vertex v, calculate its shortest distance by applying the `min` formula, using the already-computed `dist` values of its predecessors.

This paragraph explicitly connects the algorithm to the core idea of dynamic programming. The main problem ("find all shortest paths") is broken down into a collection of smaller subproblems, where each subproblem is: "what is the shortest distance to node u?". The algorithm solves these subproblems one by one in a specific order (the linearized order), starting with the smallest subproblem (dist(s)) and using its answer to help solve the next ones.

This paragraph highlights the flexibility of the dynamic programming framework. The same fundamental algorithm (traversing a DAG in linear order and applying a recurrence at each node) can solve many different problems simply by changing the function being computed. Instead of a `min` of `sums` for shortest paths, you could use a `max` of `sums` to find longest paths, or a `product` to find something else entirely.

This is the central definition of dynamic programming. It is a technique built on three key ideas:

1. Break the problem into subproblems: The first step is to define the smaller pieces of the problem (e.g., `dist(u)`).
2. Solve subproblems in order: You must solve them from "smallest" to "largest," so that answers to dependencies are always ready when you need them.
3. Store and reuse solutions: Solutions to smaller subproblems are stored and used to build up solutions to larger ones.

The paragraph makes a beautiful point: for most DP problems, the DAG isn't given to you—it's an **implicit** structure where the nodes are the subproblems and the edges are their dependencies. Dynamic programming is the process of solving the subproblems in the correct topological order of this implicit DAG.

This is a transition, indicating that the text will now move from the abstract definition of dynamic programming to a concrete example to illustrate how these ideas are applied in practice.

This paragraph defines the Increasing Subsequence (LIS) problem. It's important to distinguish between a "substring" (which must be contiguous) and a "subsequence" (which can have gaps). For the sequence 5, 2, 8, 6, the subsequence 2, 6 is valid because 2 appears before 6 in the original sequence. The goal is to find the longest such subsequence where the values are strictly increasing.

This is a crucial step in finding a solution: transforming the problem into a different domain. Here, the sequence problem is converted into a graph problem. Each number in the sequence becomes a node in a graph. A directed edge is drawn from node `i` to node `j` only if `j` can follow `i` in an increasing subsequence (meaning `j` appears after `i` in the sequence and has a larger value).

This paragraph reveals the solution path. The graph we constructed is a **Directed Acyclic Graph (DAG)** because edges only point from smaller indices to larger ones, so it's impossible to form a cycle. Crucially, any path through this DAG corresponds exactly to a valid increasing subsequence. Therefore, the LIS problem has now been simplified to finding the **longest path in a DAG**—a well-understood graph problem.

This presents the core dynamic programming algorithm. Let's break down the logic:

• We define $L(j)$ as the length of the longest increasing subsequence that **ends at position** $j$.
• We iterate from $j=1$ to $n$, calculating each $L(j)$ in order.
• To calculate $L(j)$, we look at all previous nodes $i$ that could connect to $j$ (i.e., where $i < j$ and $a_i < a_j$). We find the one that has the longest path ending at it (the maximum $L(i)$ value).
• The length of the path to $j$ is then $1$ (for $j$ itself) plus the length of the best path leading into it.
• The final answer is the maximum value in our `L` array, since the longest subsequence could end at any position.

This paragraph explicitly defines why the previous algorithm is a perfect example of dynamic programming. It satisfies the key properties:

1. A collection of subproblems: Our subproblems are "What is the LIS ending at position $j$?" for all $j$ from 1 to $n$.
2. An ordering: We solve the subproblems in a specific, linear order: for $L(1)$, then $L(2)$, then $L(3)$, and so on.
3. A recurrence relation: To solve for a subproblem $L(j)$, we only rely on the answers to "smaller" subproblems—those $L(i)$ where $i < j$, which we have already calculated and stored.

This "bottom-up" approach of solving smaller pieces first and using their results to build up to the final answer is the hallmark of dynamic programming.

The runtime of this algorithm is analyzed. For each element $j$, we look at all previous elements $i < j$. In the worst case (a sorted array), every previous element is a valid predecessor. This results in a nested loop structure, giving a total runtime of $O(n^2)$. To reconstruct the actual subsequence (not just its length), we can use a `prev` array, just as in Dijkstra's algorithm. When we find the best predecessor `i` for `j`, we store it: `prev[j] = i`. After the `L` array is full, we can find the max value, start from that index, and follow the `prev` pointers backward to find the path.

This section addresses a common question: if we have a recurrence relation, why not just write a simple recursive function? The text explains this is a terrible idea for dynamic programming problems. A naive recursive implementation would re-calculate the same subproblems an exponential number of times. For example, to calculate `L(5)`, it would call `L(4)`, `L(3)`, `L(2)`, and `L(1)`. To calculate `L(4)`, it would again call `L(3)`, `L(2)`, and `L(1)`. The redundant computations explode exponentially.

This is a critical distinction between two major algorithmic paradigms:

• Divide and Conquer (e.g., Mergesort): Works well with recursion because it breaks a problem into a few, *independent* subproblems that are much smaller (e.g., half the size). The subproblems don't overlap.
• Dynamic Programming (e.g., LIS): Is needed when the subproblems are only slightly smaller (e.g., size `n-1` for a problem of size `n`) and are heavily *overlapping*. DP's power comes from using a table (or array) to store the results of subproblems, ensuring each one is calculated only once.

                \begin{algorithm}
                \caption{Breadth‑First Search}
                \begin{algorithmic}   
                \Procedure{BFS}{$G, s$}
                    \ForAll{$u \in V$}
                    \State $\text{dist}(u) \gets \infty$
                    \EndFor
                    \State $\text{dist}(s) \gets 0$
                    \State $Q \gets [s]$
                    \While{$Q$ is not empty}
                    \State $u \gets \text{eject}(Q)$
                    \ForAll{$(u,v) \in E$}
                        \If{$\text{dist}(v)=\infty$}
                        \State $\text{inject}(Q,v)$
                        \State $\text{dist}(v) \gets \text{dist}(u)+1$
                        \EndIf
                    \EndFor
                    \EndWhile
                \EndProcedure
                \end{algorithmic}
                \end{algorithm}