Dynamic Programming

Dynamic programming (DP) is not a specific algorithm so much as a strategy for avoiding wasted work. It applies whenever a problem has two properties. The first is optimal substructure: the optimal answer to the whole problem can be assembled from optimal answers to smaller versions of the same problem. The second is overlapping subproblems: when you try to solve the problem recursively, you find yourself solving the exact same smaller subproblem over and over again. Plain recursion (or "divide and conquer") already exploits optimal substructure — that's what makes something like merge sort work — but merge sort's subproblems never overlap, so there's nothing to cache. DP is what you get when you add caching to recursion that does overlap: instead of recomputing fib(5) every time it's needed, you compute it once and reuse the answer.

Two ways to write it

There are two equivalent implementation styles. Top-down memoization keeps the natural recursive structure of the brute-force solution, but wraps it with a cache (a dictionary or array) that stores the answer to each subproblem the first time it's computed, and returns the cached value on every later call. This is usually the easiest style to derive, because you write the recursion exactly as you'd think about the problem in English, then bolt a cache onto it. Bottom-up tabulation instead builds an explicit table (usually an array or 2D grid) and fills it in order, from the smallest subproblems up to the final answer, so that every value a cell depends on has already been computed by the time you reach it. Tabulation avoids recursion overhead and stack-depth limits, and it's often what you want in an interview once you understand the recurrence, but memoization is frequently the faster path to a first correct solution, especially when the set of "reachable" subproblems is smaller than the full table.

A systematic design process

Rather than guessing, it helps to answer four questions in order for any new DP problem:

1. Define the state. What does dp[i] (or dp[i][j]) actually mean, in a sentence? For example, "dp[i] is the maximum sum of a subarray ending at index i." Getting this definition precise is most of the battle — everything else follows from it.
2. Write the recurrence. How does dp[i] relate to smaller states like dp[i-1] or dp[i-1][j-1]? This is the transition, and it usually mirrors the "if I make this one choice, what's left" logic of the brute-force recursion.
3. Identify the base case(s). What are the smallest inputs where the answer is obvious without recursing further (empty string, zero items, a single stair)?
4. Decide the fill order. For tabulation, make sure every cell you read has already been written — typically left-to-right, top-to-bottom, or smallest-subproblem-first.