Dynamic Programming on Directed Acyclic Graph (DP on DAG)

Dynamic Programming on Directed Acyclic Graph (DP on DAG)

Introduction

Dynamic programming works when a large problem can be built from smaller states whose answers are already known. On an array, the natural order is often left to right. In a directed acyclic graph, there is no single numeric order, but the edges themselves describe the dependencies.

If an edge goes from $v$ to $u$, a transition may use the answer at $v$ to improve the answer at $u$. We therefore need to process $v$ before $u$. A topological order gives exactly this guarantee.

We already learned how to construct this order in the Topological Sorting lecture. In this lecture, we use it as a known tool and focus on the dynamic programming part.

DP on a DAG is useful for longest paths, counting paths, minimum or maximum costs, scheduling with prerequisites, and many other problems where states form a directed dependency graph. By the end of this lecture, we will know how to define a state, derive its transition, choose the correct topological direction, and implement the complete solution.