Algorithmica Notebook

Appearance

From Traversal to Optimization ​

You are here: Ch 3 (Graph Foundations) --> Ch 4 (Dynamic Programming) | Core Path

What You've Learned ​

Chapter 3 gave you the tools to explore structure: BFS for shortest paths in unweighted graphs, DFS for connectivity and cycles, Dijkstra for weighted shortest paths, topological sort for dependency ordering, and MST algorithms for minimum-cost connectivity.

The graph algorithms in Chapter 3 already optimize specific things — Dijkstra minimises path cost on non-negative graphs, MST minimises total tree weight, shortest-path-on-DAG handles longest paths too. The real distinction is not "graphs don't optimize" but rather what kind of graph the algorithm runs on:

  • Chapter 3 algorithms operate on an explicit input graph — nodes and edges are given by the problem.
  • DP usually constructs an implicit decision graph — each node is a partial state of the solution, each edge is a legal choice, and the topological order is the order in which states are computed.

Once the graph is implicit, you can ask new questions. Counting paths, choosing items under a weight limit, optimising over decisions that depend on previous decisions — Dijkstra and BFS have nothing to say about those, because they assume the graph is handed to you. DP builds the graph from the problem's decision structure and then runs the same kind of edge-relaxation you already know.

That's where dynamic programming comes in.

And DP isn't some alien concept dropped from nowhere. It grows directly out of graph thinking. If you understand topological sort and edge relaxation, you already understand the mechanics of DP. What's new is learning to see DP problems -- to identify the state space, define the transitions, and trust the recurrence.

The Bridge You've Already Crossed ​

If you've read Chapter 3 carefully, you've already seen DP. It was hiding in section 6: DP on DAGs.

Here's what happened there. You had a DAG -- a directed acyclic graph. You ran topological sort to get an ordering of the nodes. Then you walked through that ordering, and at each node, you computed something based on the answers you'd already computed for its predecessors.

That's it. That's DP.

Topological sort tells you the order to process nodes -- an order where every dependency comes first. DP fills in the values along that order. The two are inseparable: topo sort is the skeleton, DP is the flesh.

Think of it this way. BFS explores a graph level by level, asking "what can I reach?" DP explores a graph in dependency order, asking "what's the best I can do?" DP is BFS with a spreadsheet.

There's another way to see the connection. In Chapter 3, you learned that Dijkstra's algorithm uses relaxation: for each edge (u, v), check if going through u gives a better path to v. DP does the exact same thing -- but it doesn't need a priority queue, because the topological order guarantees that when you process a node, all its predecessors are already finalized. No re-visiting, no re-relaxing. One clean pass.

Three Problems at the Boundary ​

Longest path in a DAG. You know shortest path: relax edges in topological order. Longest path is identical -- just flip the relaxation. At each node u, for each neighbor v: dp[v] = max(dp[v], dp[u] + weight(u,v)). The graph structure gives you the transitions. The topo order ensures you never use an answer that hasn't been computed yet. This is graph thinking and DP fused into one.

Note what's different from Dijkstra: Dijkstra can find shortest paths in graphs with cycles, but it can't find longest paths at all (that's NP-hard in general). On a DAG, though, the topological order eliminates the need for Dijkstra's priority queue. You just walk the topo order and relax. Simpler, faster, and it works for both shortest and longest paths.

State: the current node v. Transition: for each incoming edge (u,v,w), relax dp[v]←max(dp[v],dp[u]+w). Order: the topological order of the input DAG. Value: dp[v] = length of the longest path ending at v.

Number of paths in a grid. A grid where you can only move right or down. How many paths from the top-left to the bottom-right?

There's no explicit graph here -- no adjacency list, no edges. But there's an implicit DAG: cell (i,j) has edges to (i+1,j) and (i,j+1). The topological order is just row-by-row, left-to-right. And the recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1]. You're doing DP on a graph you never bothered to build.

This is the first hint that DP can exist without any graph structure in the input. The graph is in the state space -- the set of all possible partial solutions and the transitions between them. The grid just happens to make that state space obvious.

State: a cell (i,j). Transition: dp[i][j]←dp[i−1][j]+dp[i][j−1] (moves from above or from the left). Order: rows top-to-bottom, columns left-to-right (the topological order of the implicit DAG). Value: dp[i][j] = number of paths from (0,0) to (i,j).

The 0/1 Knapsack. You have n items, each with a weight and a value. You have a bag that holds at most W weight. Maximize total value.

There's no graph here at all -- no nodes, no edges, no adjacency. But think about it differently. Define a state as (item index, remaining capacity). From state (i, w), you can go to (i+1, w) by skipping item i, or to (i+1, w - weight[i]) by taking it. Those transitions form a DAG. And dp[i][w] is just the longest path in that DAG.

The graph was there all along -- you just had to look at the state space instead of the input. This is the key conceptual leap of DP: the "graph" isn't given to you. You construct it from the problem's decision structure. Every choice you can make is an edge. Every partial state is a node. And the DP recurrence is just the edge-relaxation rule.

State: (i,w) — items considered so far, capacity remaining. Transition: dp[i+1][w]←max(dp[i+1][w],dp[i][w]) (skip item i); if w≥wti, also dp[i+1][w−wti]←max(…,dp[i][w]+vali) (take it). Order: i from 0 to n; for each i, all values of w. Value: dp[i][w] = best value achievable considering the first i items with w capacity already spent.

DP doesn't need a graph. But thinking of DP states as nodes and transitions as edges helps you design the recurrence.

When you're stuck on a DP problem, ask yourself:

  • What are my states? (These are the nodes.)
  • What are my transitions? (These are the edges.)
  • What is the order of computation? (This is the topological sort.)
  • What value am I computing at each state? (This is the DP table.)
  • What is the base case? (These are the source nodes with no incoming edges.)

If you can answer those five questions, you can write the DP. The graph framework you built in Chapter 3 gives you the vocabulary. Chapter 4 gives you the practice.

You already understand traversal. You already understand ordering. Now you'll learn to attach decisions to those traversals -- to choose, at each step, the option that leads to the globally optimal answer.

What to Expect ​

Chapter 4 starts with 1D DP -- the simplest state spaces, where states are integers and transitions look left. Then it builds: 2D states (knapsack, LCS), intervals, bitmasks, digits, trees. Each new DP type is a new shape of state-space graph. But the core idea never changes: define states, define transitions, fill in topological order, read off the answer.

The problems get harder. The state spaces get larger. You'll learn to optimize DP with convex hull trick, divide and conquer, and other techniques that exploit structure in the transitions. But the foundation is always the same five questions: states, transitions, order, values, base cases.

Most students find DP the hardest topic in competitive programming. Not because the code is complex -- a DP solution is usually under 30 lines. The hard part is the design: choosing the right states, the right transitions, the right order. Chapter 4 builds that skill problem by problem, from the simple to the sublime.

Before You Move On ​

Can you confidently:

  • [ ] Implement BFS and DFS from scratch and know when to use which?
  • [ ] Run Dijkstra's algorithm and explain why it's correct?
  • [ ] Perform topological sort and detect cycles in a directed graph?
  • [ ] Compute shortest/longest paths on a DAG using topo sort + relaxation?
  • [ ] Build an MST with Kruskal's algorithm using DSU?
  • [ ] Recognize when a problem is a graph problem in disguise?

If not, revisit Chapter 3. DP thinking grows directly from graph traversal and topological ordering.

Key Files ​

Chapter 3 (just completed):

Chapter 4 (starting now):

Practice: Ladder: DP

Next: Chapter 4 -- Dynamic Programming ​

Built for the climb from Codeforces 1100 to 2100.

Algorithmica Notebook