Dynamic programming is a way to solve problems by breaking them into overlapping subproblems, solving each subproblem once, and reusing the answers. For beginners, the hard part is not the code; it is knowing what to store and how the pieces connect. This guide to dynamic programming for beginners gives you a five-step method you can apply to almost any DP problem, with worked examples in Python.

What is dynamic programming?

A problem is a good fit for dynamic programming when it has two properties:

  • Optimal substructure: the best answer for the whole problem can be built from the best answers to smaller versions of it.
  • Overlapping subproblems: a naive recursive solution solves the same smaller problem many times.

If only the first property holds, you probably want plain recursion or divide and conquer. If only the second holds, caching might help but there is nothing to optimize. When both hold, DP turns an exponential search into a polynomial one.

Why naive recursion is slow

Consider the Fibonacci sequence. The recursive definition fib(n) = fib(n - 1) + fib(n - 2) looks harmless, but fib(5) calls fib(3) twice, fib(2) three times, and so on. The call tree roughly doubles at each level, giving about O(2^n) calls. Storing each result the first time it is computed collapses that to O(n). That single idea, "never compute the same thing twice", is all DP is.

The five-step method for solving DP problems

Most beginners try to jump straight to a table. Instead, work through these steps in order and write each one down before coding:

  1. Define the state. Write a sentence of the form "dp[i] is the answer to the problem restricted to ..." The state must capture everything needed to make future decisions.
  2. Write the recurrence. Express dp[i] in terms of smaller states. Ask: "What is the last decision I make, and what are my options for it?"
  3. Identify base cases. Which states can you answer directly without recursion?
  4. Choose an evaluation order. Either recurse with a cache (top-down) or fill states so that every dependency is ready before it is used (bottom-up).
  5. Locate the answer and optimize space. Decide which state holds the final answer, then check whether you only need the last few rows or values.

The "last decision" question in step 2 is the most useful habit you can build. It turns vague problems into concrete choices.

Worked example: climbing stairs

You can climb 1 or 2 steps at a time. How many distinct ways are there to reach step n?

  • State: dp[i] is the number of ways to reach step i.
  • Recurrence: the last move was either a 1-step from i − 1 or a 2-step from i − 2, so dp[i] = dp[i - 1] + dp[i - 2].
  • Base cases: dp[0] = 1 (one way to stand still) and dp[1] = 1.
  • Order: increasing i.
  • Answer: dp[n]. Since each state uses only the previous two, you need just two variables.

That problem is Fibonacci in disguise, which is exactly the point: many DP problems share a handful of underlying shapes.

Memoization vs tabulation

There are two standard ways to implement the same recurrence. Both have the same time complexity; they differ in style and practical trade-offs. The memoization and tabulation guide covers them in more depth.

Aspect Memoization (top-down) Tabulation (bottom-up)
How it works Recursive function plus a cache Iterative loops filling a table
States computed Only those actually reached Usually every state
Ease of writing Closest to the recurrence Requires choosing a fill order
Stack risk Deep recursion can overflow No recursion
Space optimization Harder Often easy (keep last rows only)

A practical approach is to write memoization first to confirm the recurrence is correct, then convert to tabulation if you need to avoid recursion limits or reduce memory.

Worked example: coin change (minimum coins)

Given coin denominations and a target amount, return the fewest coins needed to make that amount, or −1 if it is impossible.

  • State: dp[a] is the minimum number of coins to make amount a.
  • Recurrence: the last coin used is some coin c with c ≤ a, so dp[a] = 1 + min(dp[a - c]) over all such coins.
  • Base case: dp[0] = 0.
  • Order: increasing amount, so dp[a - c] is always ready.
  • Answer: dp[amount], or −1 if it is still infinity.
from functools import lru_cache
from math import inf


def min_coins_memo(coins: list[int], amount: int) -> int:
    @lru_cache(maxsize=None)
    def solve(a: int) -> float:
        if a == 0:
            return 0
        best = inf
        for c in coins:
            if c <= a:
                best = min(best, 1 + solve(a - c))
        return best

    result = solve(amount)
    return -1 if result == inf else int(result)


def min_coins_table(coins: list[int], amount: int) -> int:
    dp = [0] + [inf] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return -1 if dp[amount] == inf else int(dp[amount])


print(min_coins_table([1, 3, 4], 6))  # 2 (3 + 3)
print(min_coins_memo([2], 3))         # -1

Both versions run in O(amount × number of coins) time. The tabulated version uses O(amount) space and has no recursion depth problem, which matters because Python's default recursion limit is fairly low. Notice the example [1, 3, 4] with amount 6: a greedy "take the biggest coin" strategy picks 4 + 1 + 1 (three coins), while DP finds 3 + 3 (two coins). That gap is why coin change is a DP problem and not a greedy one. The coin change guide explores the counting variant as well.

Common dynamic programming patterns

Once you have solved a few problems, you will notice that states tend to fall into a small number of families:

  • 1D linear: dp[i] depends on a few earlier indices. Examples: climbing stairs, house robber, decode ways.
  • 2D grid or two sequences: dp[i][j] over a grid or over prefixes of two strings. Examples: unique paths, edit distance, longest common subsequence.
  • Knapsack: dp[i][capacity] deciding whether to take item i. Examples: 0/1 knapsack, partition equal subset sum.
  • Intervals: dp[l][r] over a subarray. Examples: burst balloons, matrix chain multiplication.
  • State machine: extra dimensions for modes like "holding a stock" or "in cooldown".

When you meet a new problem, ask which family it resembles. The guides on 1D dynamic programming and 2D dynamic programming walk through each family with practice problems.

Mistakes beginners make with DP

  • Vague state definitions. If you cannot say in one sentence what dp[i] means, the recurrence will be wrong.
  • Missing information in the state. If two different situations map to the same state but need different answers, add a dimension.
  • Wrong fill order. In tabulation, reading a cell before it is computed silently produces garbage.
  • Off-by-one base cases. Decide whether indices refer to "first i items" or "item at index i" and stick with it.
  • Optimizing space too early. Get a correct full table first; compress rows afterward.

Key takeaways

  • Use DP when a problem has optimal substructure and overlapping subproblems.
  • Always define the state in words before writing any code.
  • Build the recurrence by asking what the last decision is and what options it has.
  • Memoization is easiest to write; tabulation avoids recursion limits and simplifies space optimization.
  • Most problems belong to a few families: linear, grid, knapsack, interval, and state machine.

Frequently asked questions

Is dynamic programming hard to learn?

It feels hard because problems look different on the surface, but the method underneath is consistent. If you practice defining the state and writing the recurrence explicitly for each problem, the patterns become familiar after a few dozen examples. Start with 1D problems before moving to grids and knapsack.

What is the difference between recursion and dynamic programming?

Recursion is a technique for expressing a problem in terms of smaller instances of itself. Dynamic programming adds the rule that each distinct subproblem is solved only once, either by caching recursive results or by filling a table. Plain recursion on overlapping subproblems is often exponential; DP makes it polynomial.

Should I use memoization or tabulation in interviews?

Either is acceptable. Memoization is usually faster to write correctly because it mirrors the recurrence directly. Mention that you can convert to tabulation if recursion depth or memory becomes a concern, and do so if the interviewer asks for it.

How do I know a problem needs dynamic programming?

Look for questions asking for a count of ways, a minimum or maximum value, or whether something is possible, especially over sequences, grids, or choices. If a brute-force solution would try many overlapping combinations, DP is a strong candidate.