Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Dynamic Programming

Solve each distinct subproblem once and reuse it.

time O(states × transition)space O(states)

What it is

When a recursion revisits the same states, cache the answers. Cost is (number of states) × (work per state). Top-down memoization is easiest to write; bottom-up tabulation allows space optimization.

When to reach for it

  • Overlapping subproblems
  • Optimal substructure
  • Count ways, min cost, max value, feasibility

Clues in the problem

  • Naive recursion is exponential
  • State can be described by one to three integers

Template

from functools import lru_cache
def solve(n):
@lru_cache(None)
def go(i):
if i <= 1:
return i
return go(i - 1) + go(i - 2)
return go(n)

Practice problems

  • Climbing Stairs
  • House Robber
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack

Common mistakes

  • State that misses a dimension the answer depends on
  • Recursion depth limits in Python or Java
  • Keeping the whole table when only the last row is needed