Dynamic Programming

Dynamic programming is a technique one may apply to a certain class of problems that:

1. Can be broken down into sub-problems
2. The solution to one (or usually, more) “prior” sub-problems is directly useful to solve a “current” one.
3. There is some directionality to point (2): once a sub-problem is solved, “future” sub-problems will not affect its output.

Point (2) means that dynamic programming problems can usually be expressed with a recurrence relation, and point (3) means these recurrence relations can be efficiently solved by caching answers to prior problems.

Longest Path in a Directed Acyclic Graph

When finding the longest path in a DAG, we can take inputs $Edge(a, b)$ (giving the weight from $a \to b$), $Pred = \text{ Predecessors}(n)$, (gives the set of nodes with edges ending in $n$), the recurrence relation is:

$s_b = \max_{a \in Pred(b)} \lbrace s_a + Edge(a, b) \rbrace$

To meet the dynamic programming constraints, one must find a topological ordering for computing these scores.

The nodes $a_1, \ldots, a_k$ are ordered topologically $\iff$ every edge $\lbrace a_i, a_j \rbrace$ connects a node with a smaller index to a node of larger index ($i < j$). All DAGs must have a topological sort¹ (since they are Acyclic; non-topological orderings require a cycle).

To find the max score:

$ \text{procedure }LongestPath(nodes, edges, source, sink)\newline \text{ set } s_i = -\infty \text{for } i \in nodes \newline \text{ set } s_{source} = 0 \newline \text{ for } i \in TopographicalSort(nodes) \newline \text{ set } s_i = \max_{a \in Pred(i)} \lbrace s_a + Edge(a, i) \rbrace \newline \text{ end} \newline \text{ return } s_{sink} \newline \text{endprocedure } $

To reconstruct the maximum scoring path, one can keep track of the maximum-scoring predecessor at each step, and then “back-track” the path from the highest scoring node, back to the source.