Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

From a recursion tree to a graph of subproblems

Lesson · 10 min read · Dynamic programming · Introduction to dynamic programming

Dynamic programming is recursion that refuses to solve the same subproblem twice. The recursion tree collapses into a graph of distinct subproblems.

Every DP solution starts as a recursion

Count the paths through a grid from the top-left corner to the cell (r, c), moving only down or right. The last move into (r, c) came either from above or from the left, so

paths(r, c) = paths(r − 1, c) + paths(r, c − 1), with paths(0, c) = paths(r, 0) = 1.

Written as a recursive function this is correct, and it is a perfect description of the problem. Its recursion tree shows what it does: the root is the question asked, every internal node is a smaller question of the same kind, the leaves are base cases with known answers, and answers flow upwards, each parent combining its children.

2,21,20,21,10,11,02,11,10,11,02,0
The recursion tree of paths(2, 2). Red nodes are questions that have already been asked elsewhere in the tree.

Overlapping subproblems

Even this tiny tree asks paths(1, 1) twice. For paths(10, 10) the tree has 369,511 nodes, but only 121 different questions in it: one per cell of an 11 × 11 grid. Nearly all of the work is repeated work.

Dynamic programming is the decision to answer each distinct question once and reuse the answer. When repeated nodes are merged, the tree collapses into a directed acyclic graph of subproblems: each node is computed once and feeds every parent that needs it. The work is now proportional to the number of distinct subproblems, not the size of the tree.

2,21,20,21,10,11,02,11,12,0
With memoisation: a repeated question (green) is answered from memory and not expanded again.

When dynamic programming applies

Two properties together make a problem a DP problem:

  • Optimal substructure. The answer to a problem can be built from the answers to smaller problems of the same kind. The best route to (r, c) is the best route to one of its predecessors plus one move; the fewest coins for amount a is one coin plus the fewest coins for what remains.
  • Overlapping subproblems. The recursion asks the same smaller questions many times. Without this, memoisation saves nothing and plain recursion (or divide and conquer, as in merge sort) is enough.

A useful test: write the brute-force recursion, then count its distinct argument tuples. If that number is polynomial and the recursion tree is exponential, dynamic programming will make it fast.

The next four modules turn this into a procedure that works on every problem in this chapter: choose the state, write the recurrence, settle the base cases, and pick an order in which to compute.