Dynamic Programming Explained Visually: Memoization, Tabulation, and the Patterns That Stick

What dynamic programming actually is

Dynamic programming is a technique for solving problems by breaking them into smaller subproblems, solving each subproblem once, and storing the result so it doesn't get recomputed. That's the complete definition.

Two properties must be present for DP to apply:

Memoization vs tabulation — the visual difference

There are two ways to implement DP. They produce the same result but think about the problem in opposite directions. Fibonacci is the simplest example to see them both.

Memoization — top-down

Start with the original recursive solution. Add a cache. Before computing a subproblem, check if the answer is already in the cache. If yes, return it immediately. If no, compute it, store it, and return it.

function fib(n, memo = {}) {
  if (n in memo) return memo[n];   // cache hit — no recomputation
  if (n <= 1) return n;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

With memoization, fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). But the second call to fib(3) is already in the cache — it returns in O(1). The exponential tree collapses into a linear chain of unique calls.

Tabulation — bottom-up

Forget recursion. Build a dp array starting from the base cases and fill it up to the answer. You're solving subproblems in order, smallest first, until you reach the target.

function fib(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];  // each cell uses the two before it
  }
  return dp[n];
}

The dp array for fib(7) filling up — each cell depends on the two before it:

In interviews, start with memoization if you're unsure — it's easier to derive from the recursive solution you already wrote. Convert to tabulation as a follow-up if the interviewer asks for an iterative approach or to reduce stack space.

Dynamic programming examples, step by step

The fastest way to build DP intuition is to watch the dp array fill up on concrete examples. Here are the three problems that every interviewer expects you to understand deeply.

Coin Change — minimum coins to reach a target

Given coins [1, 3, 4] and amount 6, find the minimum number of coins to make exactly 6.

The recurrence: dp[i] = min(dp[i - coin] + 1) for each coin. For each amount i, try every coin and take the minimum.

dp array filling up — coins = [1, 3, 4], amount = 6:

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;  // base case: 0 coins to make amount 0

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

House Robber — non-adjacent maximum sum

Given an array of house values, find the maximum amount you can rob without robbing two adjacent houses. This is the canonical linear DP problem — the decision at each house is binary: rob it or skip it.

The recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). At each house, the best you can do is either skip it (take dp[i-1]) or rob it and add its value to the best result two houses back.

Houses = [2, 7, 9, 3, 1]:

Longest Common Subsequence — the 2D dp table

LCS introduces the 2D dp table — a grid where rows represent one string and columns represent the other. Each cell dp[i][j] stores the LCS length for the first i characters of string A and the first j characters of string B.

The recurrence: if characters match, dp[i][j] = dp[i-1][j-1] + 1. If they don't, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). The table fills left-to-right, top-to-bottom, and the answer sits in the bottom-right cell.

The 5 DP patterns you need for coding interviews

Most DP problems in interviews are variations of five structural patterns. Recognizing the pattern is the hardest part — the implementation follows naturally once you see it.

Is this a DP problem? The decision framework

When you see a new problem in an interview, run through these two questions before deciding on DP. Verbalizing this process shows the interviewer you have a systematic approach — not just pattern-matched to "use DP."

Additional signals to watch for

• ✓The problem asks for the maximum, minimum, longest, or shortest of something — classic DP output.
• ✓The problem asks "how many ways" to do something — counting DP.
• ✓The problem asks whether something is possible (true/false) — boolean DP, often knapsack.
• ✓A greedy approach almost works but fails on edge cases — DP is usually the correct solution.
• ✓The constraint on n is ≤ 1000 or ≤ 10000 — O(n²) DP is feasible, O(2ⁿ) backtracking is not.

How to study DP so it actually sticks

DP has the highest rate of "I understood the solution but couldn't reproduce it" of any topic in interview prep. The reason is almost always the same: people study the code, not the process. Here's what works instead:

1. Write the brute-force recursion first. Don't jump to the DP solution. Write the naive exponential recursive solution without caching. Once it works, the memoized version is just adding a cache. Once the memoized version works, the tabulated version is just reversing the direction. Each step is a small, motivated change.
2. Draw the dp array or dp table before writing code. For 1D problems, draw the array and fill in values by hand for a small input. For 2D problems, draw the grid. The recurrence becomes obvious from the pattern of how cells depend on each other. This step takes 2 minutes and saves 20 minutes of confusion.
3. Watch the execution, not just the code. Static code shows you the final state. Watching the dp array fill up step by step — cell by cell, with each transition animated — builds the mental model that makes DP feel intuitive, not mechanical. This is the gap between candidates who memorize DP and candidates who understand it.
4. Practice pattern recognition, not problem memorization. After solving a problem, write one sentence identifying the pattern: "This is unbounded knapsack because I can use each coin unlimited times." Train the recognition reflex. In an interview, you'll have 5 minutes to identify the approach — that sentence is what you're building toward.
5. Do problems in clusters, not randomly. Solve 5 linear DP problems in a row before moving to knapsack. Solve 5 knapsack problems before moving to string DP. Interleaving problem types feels more comprehensive but produces shallow pattern recognition. Blocked practice produces transfer.

Frequently asked questions

Summary

Dynamic programming is not a collection of tricks to memorize — it's a systematic approach to a specific class of problems. The key insight is always the same: if your recursive solution solves the same subproblem more than once, cache the result. If you can identify the recurrence, you can build the dp array.

The difference between candidates who find DP approachable and candidates who fear it is not intelligence — it's the study method. Watching DP execute visually, drawing the dp table before coding, and practicing by pattern clusters produces transfer. Reading finished solutions produces fragile recall.

Start with Fibonacci. Watch it go from exponential recursion to memoization to tabulation. Once that transition clicks, every other DP problem is a variation of the same story.