Dynamic Programming Demystified: A Step-by-Step Approach

If dynamic programming gives you a sinking feeling every time it appears in a coding round, you are not alone. Most candidates understand recursion well enough but hit a wall when problems require storing and reusing past computations. This guide covers what DP actually is, how to spot it in a dynamic programming interview, and a repeatable method for solving it from scratch.

Quick answer: Dynamic programming is a technique for solving problems that have two properties: overlapping subproblems (the same sub-calculation is needed multiple times) and optimal substructure (the best answer to the whole problem can be built from best answers to smaller ones). You solve each subproblem once, store the result, and reuse it. The two implementations are memoization (top-down recursion with a cache) and tabulation (bottom-up iteration with a table). When a brute-force recursion recomputes the same inputs repeatedly, DP is almost certainly the right tool.

What Is Dynamic Programming?

Dynamic programming, usually abbreviated DP, is not a data structure or a single algorithm. It is a problem-solving strategy that applies when two properties hold simultaneously.

Overlapping subproblems: the problem splits into smaller subproblems, and those subproblems recur across different branches of the recursion. In a naive recursive Fibonacci calculation, fib(3) is recomputed from scratch every time it is needed. DP stores the result the first time and looks it up on every subsequent call.

Optimal substructure: the optimal solution to the full problem can be assembled from optimal solutions to its subproblems. Shortest path problems have this property: the shortest route from A to C via B is the shortest route from A to B plus the shortest route from B to C.

When both properties hold, DP converts an exponential brute-force into a polynomial-time solution by caching work already done.

DP vs Greedy vs Divide-and-Conquer

These three techniques are frequently confused, and interviewers test whether you can tell them apart.

• Divide-and-conquer (merge sort, quicksort) splits a problem into independent subproblems. DP subproblems overlap.
• Greedy makes the locally best choice at each step without reconsidering. DP explores all choices and picks the global optimum.

DP is generally slower than greedy but correct in situations where greedy fails. Coin change with arbitrary denominations is a classic counter-example: greedy picks the largest coin that fits at each step, which often gives the wrong answer. DP finds the true minimum. Knowing this distinction is worth memorising before any dynamic programming interview.

How to Recognise a Dynamic Programming Problem

There is no single diagnostic signal, but several patterns show up repeatedly in DP problems.

The problem asks for a minimum, maximum, count, or yes/no decision over a set of choices, not "print all possible solutions" (enumeration of all paths is usually exponential and does not benefit from caching).

A naive recursive solution has repeated sub-calls with identical arguments. Sketch a small recursion tree: if the same node appears more than once with the same parameters, the problem is a DP candidate.

The problem involves sequences (strings, arrays), grids, or subsets where a choice at one index constrains choices at later indices.

The problem description contains words like "longest", "shortest", "minimum cost", "number of ways", "can you reach", or "partition". These vocabulary signals are reliable but not universal.

Common DP problems you will encounter include: climbing stairs, coin change, 0/1 knapsack, longest common subsequence, edit distance, maximum subarray, unique paths, and word break. Recognising a new problem as a variant of a known pattern lets you adapt rather than start from scratch.

The Four-Step DP Method

Once you identify a problem as a DP problem, apply this method consistently. Every step should be spoken out loud before you open a code editor.

Step 1: Define the state. Decide what dp[i] (or dp[i][j] for 2D) represents. Be precise and write it down. For coin change: "dp[a] = the minimum number of coins needed to make exactly amount a." Getting this wrong makes the rest of the solution impossible to verify. Interviewers who see a candidate define the state clearly usually award that as a positive signal, even if the code has a small bug.

Step 2: Write the recurrence. Express dp[i] in terms of earlier (smaller) states. For coin change, if coins is the set of denominations: dp[a] = min(dp[a - c] + 1) for each coin c where c <= a. This recurrence is the heart of the solution. Every subsequent choice follows from it.

Step 3: Identify the base cases. What is true without any computation? For coin change: dp[0] = 0 (zero coins are needed to make amount zero). All other entries start at infinity, representing "no solution found yet." For string or array problems, the base case is usually the empty string or empty array.

Step 4: Decide the computation order. Bottom-up tabulation fills the table from smaller to larger values so that every dependency is resolved before it is needed. Top-down memoization handles ordering automatically via the recursion call stack. For most 1D DP, left to right is safe. For 2D DP (grids, LCS), row-by-row works.

Writing these four steps explicitly in an interview, even in pseudocode, is what separates a structured DP answer from a lucky guess.

Memoization vs Tabulation

Both approaches solve the same DP problem and produce identical results. The difference is implementation style and trade-offs that matter in practice.

Approach      | Direction   | Space      | Stack risk
--------------+-------------+------------+-----------
Memoization   | Top-down    | O(states)  | Yes (deep)
Tabulation    | Bottom-up   | O(states)  | No

Memoization keeps your recursive intuition intact. You write the natural recursion, then add a cache (a dictionary or array) that stores each result before returning. If the cache already holds the answer for a given input, return it immediately without recursing further. This approach is often faster to write in an interview because the logic mirrors how you think about the problem.

Tabulation builds the answer iteratively. You allocate a table, fill in base cases, then fill remaining entries using the recurrence, usually left to right or row by row. It avoids recursion depth limits, uses the call stack more efficiently, and is generally faster in practice due to lower function-call overhead.

A practical interview move: start by explaining the memoized version to show you understand the recursion clearly, then offer to convert it to tabulation for production code or if the interviewer asks about stack depth.

Both approaches have the same asymptotic time and space complexity for a given problem. The difference is constant factors and stack safety.

Worked Example: Coin Change

Problem: given coins [1, 3, 4] and a target amount of 6, find the minimum number of coins that sum to exactly 6.

State: dp[a] = minimum coins to make amount a.

Recurrence: dp[a] = min(dp[a - c] + 1) for each coin c where c <= a.

Base case: dp[0] = 0. All other entries initialised to infinity.

Computation order: fill dp[1] through dp[6] left to right. Each cell depends only on cells to its left, so the order is always safe.

Here is the table being filled, step by step:

coins = [1, 3, 4],  target = 6

 Amount |  0   1   2   3   4   5   6
--------+-------------------------------
 dp[]   |  0   1   2   1   1   2   2

Fill:
  dp[1] = dp[0]+1 = 1          (coin 1)
  dp[2] = dp[1]+1 = 2          (coin 1 again)
  dp[3] = min(dp[2]+1=3,
              dp[0]+1=1) = 1   (coin 3)
  dp[4] = min(dp[3]+1=2,
              dp[0]+1=1) = 1   (coin 4)
  dp[5] = min(dp[4]+1=2,
              dp[2]+1=3,
              dp[1]+1=2) = 2   (coins 4+1)
  dp[6] = min(dp[5]+1=3,
              dp[3]+1=2,
              dp[2]+1=3) = 2   (coins 3+3)

Answer: 2 coins. The tabulated Python solution:

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Time complexity: O(amount * len(coins)). Space complexity: O(amount). Both numbers are worth stating out loud before moving to code. Interviewers expect this and often follow up with "can you reduce the space?" For coin change, you cannot because you need the full 1D table. That is a correct and honest answer.

Common DP Patterns

Most DP problems in coding interviews belong to a small set of pattern families. Knowing the pattern by name lets you adapt the state definition quickly rather than deriving everything from first principles.

0/1 Knapsack. You have items with weights and values and a bag with a weight limit. Each item is included or excluded (no fractions). State: dp[i][w] = maximum value using the first i items with weight capacity w. Recurrence: either skip item i or include it if it fits. Variants include subset sum, partition equal subset, and target sum.

Longest Common Subsequence (LCS). Given two strings, find the longest subsequence common to both (characters do not need to be contiguous). State: dp[i][j] = LCS length for the first i characters of string A and first j characters of string B. Recurrence: if characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise max(dp[i-1][j], dp[i][j-1]). Variants include edit distance and longest common substring.

Grid paths. Count all paths from the top-left to bottom-right of a grid, possibly with obstacles. State: dp[i][j] = number of ways to reach cell (i, j). Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (skip blocked cells). Unique Paths is the textbook version; minimum path sum is a direct relative.

Linear sequence. Problems like climbing stairs, house robber, and maximum subarray sit in this family. The state is a 1D array (or sometimes just a handful of variables with a rolling update). These are the best starting points when learning DP because the state space is easy to visualise.

Saying "this looks like a 0/1 knapsack variant; let me define the state the same way and adjust the recurrence" is a strong signal in any coding interview. It shows pattern recognition, not memorisation.

How to Talk Through DP in a Coding Interview

Technical correctness matters, but verbal communication is scored separately in most structured interviews, particularly at product companies and larger engineering organisations. A silent session where the interviewer cannot follow your logic rarely ends well, even if the final code is correct.

A structure that works:

1. Restate the problem in your own words and confirm constraints (input size, value ranges, expected output type).
2. State whether you think this is a DP problem and why: overlapping subproblems, optimal substructure, or recognition of a familiar pattern.
3. Define your state precisely before touching the keyboard. "dp[i] represents..."
4. Write the recurrence, either as a formula or pseudocode.
5. State the base case.
6. State time and space complexity before coding.
7. Code the solution, narrating non-obvious choices as you go.
8. Walk through a small example to verify the table values match expectations.

If you stall on the recurrence, the interviewer will often guide you. But you only get that opportunity if you are visibly working through the method, not staring at the screen in silence. Speaking while thinking is a practised skill, not a natural one. It takes deliberate repetition to build.

Frequently Asked Questions

What is the difference between dynamic programming and plain recursion? Recursion is a call mechanism: a function calls itself to break down a problem. DP is a strategy: solve each subproblem once and store the result so it is never recomputed. Memoized DP uses recursion as its implementation but adds a cache. Tabulated DP typically uses iteration. Pure recursion without caching will recompute overlapping subproblems and is usually exponentially slow for DP-class problems.

How do I know whether to use memoization or tabulation? Both give the same answer. Use memoization when the recursive formulation is easier to see and explain, or when only a subset of states is actually visited (sparse state spaces). Use tabulation when you need to avoid stack overflow on large inputs, want maximum runtime speed, or when the interviewer explicitly asks for an iterative solution. In an interview, explain both and let the interviewer's follow-up questions guide which one you implement in full.

Is it always possible to reduce the space of a DP solution? Not always, but often yes. If the recurrence only reads back a fixed number of rows or columns, you can use a rolling array. For example, coin change uses a 1D array because each cell only depends on earlier cells in the same row. LCS in its standard form can be compressed from O(m x n) to O(min(m, n)) with a two-row rolling update. Ask yourself: "which previous cells does dp[i][j] actually read?" If the answer is "only the previous row," the compression is straightforward.

Why does greedy fail for coin change with arbitrary denominations? Greedy picks the largest coin that fits at each step. With coins [1, 3, 4] and target 6, greedy selects 4, then 1+1, giving 3 coins. DP finds 3+3 for 2 coins. Greedy works for standard coin systems (canonical denominations like 1, 5, 10, 25) but fails in the general case because a locally large choice can block a globally better combination. This is why DP is necessary for arbitrary denomination sets.

How do interviewers score DP answers? Most structured rubrics score on: (1) correctly identifying the problem as DP, (2) defining the state clearly, (3) writing a correct recurrence, (4) handling base cases and boundary conditions, (5) stating complexity accurately, and (6) communicating the logic in real time. A brute-force recursive solution with a clear explanation of where caching would apply is often scored above a silent but correct tabulated answer. The reasoning matters as much as the code.

Practising DP Out Loud with Rehurz

Reading about DP is one thing. Explaining your state definition, defending your recurrence under follow-up questions like "why not greedy here?" or "what if the target is zero?", and recovering cleanly when your base case is wrong: those are separate skills that only develop through practice under pressure.

Rehurz coding rounds are built for exactly this. You pick a problem, explain your approach and walk through your recurrence before writing a single line, and get cross-questioned the way a real interviewer would. Then you write the actual solution in the language you would use on the job. The scorecard evaluates your reasoning and your code, not just whether hidden tests pass. That distinction matters: an autograder cannot tell whether you understood the recurrence or got lucky.

See how Rehurz coding rounds work, then try a Rehurz coding round with a DP problem. Your first round is free, no card required: start here.

Solving DP problems on paper sharpens your thinking. Explaining your state definition under pressure, fielding "can you reduce the space?", and recovering from a wrong base case without losing your thread: that is what the interview actually measures. Build that skill in conditions that match the real thing.