Dynamic Programming Fundamentals

What dynamic programming is

DP solves a problem by combining solutions to overlapping subproblems, computing each subproblem once and storing it. Two conditions make a problem a DP problem:

1. Optimal substructure — the answer can be built from answers to smaller instances.
2. Overlapping subproblems — the same smaller instances are needed again and again.

If subproblems don't overlap (merge sort), it's plain divide & conquer. If they do, DP turns exponential recursion into polynomial time.

From brute force to DP: climbing stairs

You can climb 1 or 2 steps. How many ways to reach step n?

1. Plain recursion — O(2ⁿ)

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

2. Memoization (top-down) — O(n)

Cache results of the recursion.

from functools import cache

@cache
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

vector<long long> memo(n + 1, -1);
function<long long(int)> ways = [&](int i) -> long long {
    if (i <= 1) return 1;
    if (memo[i] != -1) return memo[i];
    return memo[i] = ways(i - 1) + ways(i - 2);
};

3. Tabulation (bottom-up) — O(n)

Fill a table from the base cases up.

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

4. Space-optimized — O(1) space

dp[i] only needs the previous two values.

def ways(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

long long ways(int n) {
    long long a = 1, b = 1;
    for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    return b;
}

This progression — recursion → memo → table → rolling array — is how you should develop every DP solution.

The five-step recipe

Defining the state

Ask: “If I were solving this recursively, what parameters change between calls?” Those parameters are the state. Common state shapes:

Finding the transition: think about the last step

• Climbing stairs: the last step was 1 or 2 → dp[i] = dp[i−1] + dp[i−2].
• House robber: either house i is robbed (then i−1 isn't) or it isn't → dp[i] = max(dp[i−1], dp[i−2] + a[i]).
• Coin change: the last coin used was some c → dp[a] = 1 + min(dp[a − c]).
• Unique paths: the last move came from above or from the left.

Worked example: coin change

Fewest coins to make amount; unlimited supply of each coin.

1. State: dp[a] = fewest coins that sum to exactly a.
2. Transition: dp[a] = min over coins c ≤ a of dp[a − c] + 1.
3. Base: dp[0] = 0; everything else starts at ∞ (unreachable).
4. Order: increasing a.
5. Answer: dp[amount] (or −1 if ∞).

def coin_change(coins, amount):
    INF = float("inf")
    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 dp[amount] if dp[amount] != INF else -1

int coinChange(vector<int>& coins, int amount) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
    return dp[amount] >= INF ? -1 : dp[amount];
}

O(amount × coins) time, O(amount) space.

Top-down vs bottom-up

Start with memoization if the order is unclear; convert to tabulation when you need speed or less memory.

Space optimization

If dp[i] depends only on dp[i−1] (and maybe dp[i−2]), keep just those rows/values.

• 1D → a few variables.
• 2D where row i depends only on row i−1 → two rows, or one row updated carefully.
• Direction matters for single-row updates: 0/1 knapsack iterates capacity backwards so each item is used once; unbounded knapsack iterates forwards. See Knapsack.

Counting vs optimizing vs deciding

The same state space can answer different questions by changing the combine operation:

Reconstructing the solution

To return the actual choices (not just the value), either store a parent/choice array during the fill, or walk the finished table backwards re-checking which transition produced each value.

How to practise DP

1. Always write the state in words first.
2. Solve the recursive version, then memoize, then tabulate.
3. Draw the table for a small example by hand.
4. Learn the families: 1D, 2D/strings, knapsack, interval/tree/bitmask/digit.

Watch an LCS table fill in the DP visualizer.

Common mistakes

• Vague state definitions ("dp[i] is the answer for i") — be precise about inclusive/exclusive and "ending at".
• Wrong base cases (off by one on empty prefix).
• Using 0 instead of ∞/−∞ for impossible states in min/max problems.
• Iterating in an order where dependencies aren't computed yet.
• Forgetting the modulo in counting problems (or applying it to a min).