← All patterns

Dynamic Programming

Express the answer as overlapping subproblems with optimal substructure; cache results. Flavors range from 1D rolling DP through 2D knapsack, interval DP, state machines, and bitmask DP.

38 problems 5 Easy 18 Medium 15 Hard

DP solves problems with overlapping subproblems and optimal substructure by caching solutions. Top-down (memoized DFS) is intuitive; bottom-up (tabulation) is space-efficient. Knowing the flavors keeps you efficient: 1D rolling (Fibonacci, climbing stairs), 2D string/array pair (LCS, edit distance), knapsack (0/1 vs unbounded — direction of inner loop), interval (palindrome partition, burst balloons), state machine (stock trading), bitmask (TSP, subset DP), and tree DP (return tuples from DFS).

The central question is always: what's the *state*? Once state is right, the recurrence falls out.

When to reach for this pattern

  • Optimization (min/max/count) where naive recursion has overlapping calls
  • 'How many ways to reach X' or 'best score reaching X'
  • Decision over a sequence where each step depends on a small lookback
  • Problem on a grid or interval with optimal substructure

Canonical template 

// 1D rolling for Fibonacci-shape recurrences
int a = base0, b = base1;
for (int i = 2; i <= n; ++i) {
    int c = transition(a, b);
    a = b; b = c;
}
return b;

// 0/1 knapsack: descend inner loop to prevent re-using items
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int x : nums)
    for (int s = target; s >= x; --s)
        dp[s] = dp[s] || dp[s - x];

// 2D LCS rolling to 1D
vector<int> dp(m + 1, 0);
for (int i = 1; i <= n; ++i) {
    int prev = 0;
    for (int j = 1; j <= m; ++j) {
        int tmp = dp[j];
        dp[j] = a[i - 1] == b[j - 1] ? prev + 1 : max(dp[j], dp[j - 1]);
        prev = tmp;
    }
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • 0/1 knapsack inner loop must go *high to low* to prevent re-using an item; unbounded goes low to high
  • Wrong base case at the empty / zero index
  • Recomputing in O(n²) when a 1D rolling array suffices
  • Forgetting long long when the state space allows overflow (counts modulo prime)

Related patterns

Backtracking Greedy Techniques Subsets

Problems (38)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.