How do I know a problem needs dynamic programming?

Write the brute-force recursive solution first, even in your head. If that recursion calls itself with the same arguments multiple times — overlapping subproblems — and the problem also has optimal substructure (the best overall answer is built from the best answers to subproblems), it is a DP problem. If the brute force never repeats work, DP will not help.

What's the difference between memoization and tabulation?

Memoization is the recursive brute force plus a cache — least effort, and the recommended starting point in an interview because it changes the least code. Tabulation builds the answer iteratively from the smallest subproblems up, using no recursion. Both have the same complexity; tabulation avoids recursion-depth limits and often uses less memory once you can drop old rows.

Is DP heavily tested at every level?

Basic one-dimensional DP (climbing stairs, house robber-style problems) shows up at SDE 1 and SDE 2. Multi-dimensional and harder DP variants are less common as levels rise — by Staff, DP is rare because the interview has shifted almost entirely to system design.

Dynamic Programming

Write the brute-force recursion first. If it calls itself with the same arguments repeatedly, that repeated work is exactly what a cache — memoization or tabulation — eliminates.

How to recognize it

The reliable test is not the problem statement — it is what happens when you sketch the brute-force recursive solution. Two properties together mean DP: overlapping subproblems (the recursion calls itself with identical arguments more than once) and optimal substructure (the best answer to the whole problem is built from the best answers to its subproblems, not from some other combination). "Count the ways to," "find the minimum/maximum," and "can you reach" phrasing over a sequence or grid are common surface signals, but the recursion check is the one that actually confirms it.

How the pattern works

Classic example: climbing stairs, where you can take 1 or 2 steps at a time, and you need the number of distinct ways to reach the top. The brute-force recursion ways(n) = ways(n-1) + ways(n-2) recomputes the same values exponentially many times. Add a cache and the exponential collapses to linear.

Python

def climb_stairs(n):
    cache = {}
    def ways(k):
        if k <= 1:
            return 1
        if k in cache:
            return cache[k]
        cache[k] = ways(k - 1) + ways(k - 2)
        return cache[k]
    return ways(n)

JavaScript

function climbStairs(n) {
  const cache = new Map();
  function ways(k) {
    if (k <= 1) return 1;
    if (cache.has(k)) return cache.get(k);
    const result = ways(k - 1) + ways(k - 2);
    cache.set(k, result);
    return result;
  }
  return ways(n);
}

Say the identification step out loud before writing any code: "the brute-force recursion for n and n-1 both end up calling ways for the same smaller values — that's the overlapping subproblem, so I'll cache it." Interviewers give real credit for that diagnostic step, separately from the code that implements it.

Common mistakes

Jumping straight to a DP table without first writing (or at least describing) the brute-force recursion the table is replacing — this usually means the recurrence relation is guessed rather than derived, and guessed recurrences are where most DP bugs come from
Getting the base cases wrong, especially off-by-one errors at index 0 and 1
Using memoization on mutable arguments (like a list) as a cache key without converting to something hashable (a tuple in Python)
Reaching for a full 2D DP table when the recurrence only ever needs the previous one or two rows — a common follow-up is "can you reduce the space," and the answer is usually yes

Complexity

Once memoized, complexity is (number of distinct subproblems) × (work per subproblem) — for climbing stairs, n distinct subproblems at O(1) work each, giving O(n) time and O(n) space for the cache. The space-optimization follow-up ("only the last two values are ever needed") drops space to O(1) — naming both the naive and optimized space bounds, and why the optimization is valid, is exactly the kind of complexity discussion covered in Time & Space Complexity.

Frequently asked questions

How do I know a problem needs dynamic programming?: Write the brute-force recursive solution first, even in your head. If that recursion calls itself with the same arguments multiple times — overlapping subproblems — and the problem also has optimal substructure (the best overall answer is built from the best answers to subproblems), it is a DP problem. If the brute force never repeats work, DP will not help.
What's the difference between memoization and tabulation?: Memoization is the recursive brute force plus a cache — least effort, and the recommended starting point in an interview because it changes the least code. Tabulation builds the answer iteratively from the smallest subproblems up, using no recursion. Both have the same complexity; tabulation avoids recursion-depth limits and often uses less memory once you can drop old rows.
Is DP heavily tested at every level?: Basic one-dimensional DP (climbing stairs, house robber-style problems) shows up at SDE 1 and SDE 2. Multi-dimensional and harder DP variants are less common as levels rise — by Staff, DP is rare because the interview has shifted almost entirely to system design.

Practice patterns weighted to your level

Free account. DSA emphasis and difficulty scale with your target level.