Dynamic Programming for Beginners: The Complete Introduction

Dynamic programming (DP) is one of the most feared topics in coding interviews — and one of the most rewarding to learn. Once you see the underlying pattern, problems that looked impossible become straightforward. This guide takes you from zero to confident with DP, covering the two core principles, the difference between top-down and bottom-up approaches, all six major DP sub-patterns, and fully worked examples you can follow line by line.

What Is Dynamic Programming?

Dynamic programming is a problem-solving technique that breaks a problem into smaller subproblems, solves each subproblem once, and stores the result so it never needs to be recomputed. It is not a single algorithm — it is a strategy that applies whenever a problem has two properties:

When both properties are present, DP can transform an exponential brute-force solution into a polynomial one — often from O(2ⁿ) to O(n) or O(n²).

When to Use DP: 3 Signals to Recognize

In an interview you have seconds, not minutes, to decide on an approach. Watch for these three signals:

1. The problem asks "how many ways" or "find the minimum/maximum." Counting and optimization problems almost always have overlapping subproblems.
2. You can express the answer recursively. If you can write a recurrence like f(n) = f(n-1) + f(n-2), DP is likely the right tool.
3. A brute-force recursion would revisit the same state. Draw two or three levels of the recursion tree. If you see repeated nodes, DP will help.

Keywords to watch for: "maximum profit", "minimum cost", "number of ways", "longest subsequence", "shortest path", "partition", "subset sum", "choose or skip".

Top-Down vs Bottom-Up

There are two ways to implement DP. Both give the same result; the choice depends on the problem and your comfort level.

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Beginner tip: Start with top-down (memoization) because it maps directly to the recursive formula. Once you are comfortable, convert to bottom-up for better performance and space optimization.

The 6 DP Sub-Patterns

Most DP problems in interviews fall into one of six families. Learning these templates lets you recognize a new problem and immediately know the state definition, recurrence, and base case.

Step-by-Step Example: Climbing Stairs

Problem: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?

Step 1: Identify the DP Signals

• "How many distinct ways" — counting problem.
• The number of ways to reach step n depends on steps n-1 and n-2 — optimal substructure.
• A naive recursion would recompute the same steps many times — overlapping subproblems.

Step 2: Brute-Force Recursion (Exponential)

def climb(n):
    if n <= 1:
        return 1
    return climb(n - 1) + climb(n - 2)

# Time: O(2^n) — way too slow for n > 30

Step 3: Add Memoization (Top-Down)

def climb(n, memo={}):
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo)
    return memo[n]

# Time: O(n), Space: O(n)

Step 4: Convert to Bottom-Up (Tabulation)

def climb(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# Time: O(n), Space: O(n)

Step 5: Optimize Space to O(1)

Since each state only depends on the two previous states, we can replace the array with two variables:

def climb(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

# Time: O(n), Space: O(1) — optimal!

This four-step progression — brute force, memoization, tabulation, space optimization — works for virtually every DP problem. Practice it until it becomes automatic.

Step-by-Step Example: 0/1 Knapsack

Problem: Given n items, each with a weight and a value, determine the maximum value you can carry in a knapsack of capacity W. Each item can be taken at most once.

Define the State

Let dp[i][w] = the maximum value achievable using items 0..i with remaining capacity w.

Write the Recurrence

For each item i with weight wt[i] and value val[i]:

• Skip item i: dp[i][w] = dp[i-1][w]
• Take item i (if wt[i] <= w): dp[i][w] = dp[i-1][w - wt[i]] + val[i]
• Take the maximum of both choices.

Bottom-Up Implementation

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]          # skip item i
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )

    return dp[n][capacity]

# Time: O(n * W), Space: O(n * W)

Space-Optimized 1D Version

Since each row only depends on the previous row, we can use a single 1D array. The trick: iterate w in reverse so that we don't overwrite values we still need:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

# Time: O(n * W), Space: O(W) — much better!

Notice the reverse iteration on w. This is the hallmark of 0/1 Knapsack. In the Unbounded Knapsack pattern, you iterate forward instead, which allows an item to be picked multiple times.

Common DP Mistakes (and How to Avoid Them)

Practice Problems by Sub-Pattern

The best way to internalize DP is to solve problems grouped by pattern. Here are curated problems for each sub-pattern, ordered from easier to harder:

Further Reading

• How to Recognize DP Problems in 10 Seconds
• Dynamic Programming Patterns Explained: A Visual Guide
• Backtracking vs DP: When to Use Which
• Top 50 LeetCode Problems Organized by Pattern