Lesson 1 · Problem-solving methods

Dynamic Programming

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into simpler, overlapping subproblems. It stores the results of these subproblems so that each is only solved once.

The Two Conditions

Dynamic programming solves a problem by breaking it into subproblems, solving each once, and reusing the stored result. It applies only when two specific properties hold, and checking them is how you decide whether DP is the right tool rather than guessing.

Overlapping subproblems means the recursion reaches the same subproblem repeatedly. Naive recursive Fibonacci computes fib(30) in about 1.6 million calls, though there are only 31 distinct values to compute — everything beyond those 31 is repeated work. Caching collapses it to 31 computations.

This is precisely what separates DP from divide and conquer. Merge sort also splits and recurses, but its halves are disjoint and never recur, so there is nothing to cache. No overlap, no DP — the technique has nothing to offer there.

Optimal substructure means an optimal solution is built from optimal solutions to its subproblems. The shortest path from A to C through B contains the shortest path from A to B; if a shorter A-to-B route existed, substituting it would improve the whole, contradicting optimality.

This condition genuinely fails sometimes, and knowing when protects you from applying DP where it produces wrong answers. Longest simple path in a graph has no optimal substructure: stitching two longest sub-paths can revisit a vertex, making the result not a simple path at all. The problem is NP-hard, and no DP formulation over the obvious states fixes that.

When both conditions hold, DP converts exponential work into polynomial by ensuring each distinct subproblem is computed exactly once.

Overlapping subproblems: the same subproblem recurs many times
No overlap means divide and conquer, not DP
Optimal substructure: optimal wholes are built from optimal parts
Longest simple path fails the second condition — DP does not apply

Defining the State

Almost all the difficulty in a DP problem lies here, and almost none in the coding. The state is the set of parameters that uniquely identify a subproblem — and choosing it well is what makes the recurrence appear almost automatically.

A workable test: if you paused the algorithm mid-way, what would you need to know to finish correctly? Nothing more belongs in the state, and nothing less will do. In the knapsack problem the answer is which item you are considering and how much capacity remains — the specific items already taken do not matter, only the capacity they consumed.

Get this wrong in either direction and the solution fails. Too little and different situations collapse into one cache entry, returning answers from the wrong context. Too much and the state space explodes, making a correct solution too slow to run.

With the state fixed, write the recurrence: how the answer at one state is built from smaller states. This usually enumerates the choices available at that state and takes the best. Knapsack has two — skip the item, keeping capacity; or take it, paying its weight and gaining its value — so the answer is the maximum of those two.

Then the base cases, which are the states with no smaller subproblem beneath them: an empty array, zero capacity, an index past the end. Getting these wrong produces solutions that are correct in the middle and wrong at the boundaries.

The complexity follows mechanically once the state is defined: number of states × work per state. Knapsack with n items and capacity W has n·W states and O(1) work each, giving O(n·W). Notice this is pseudo-polynomial — W is a value, not an input size, so a capacity of one billion makes the table impossible regardless of how few items there are.

State = what you would need to know to finish from here
Too few parameters conflate subproblems; too many explode the space
The recurrence enumerates the choices at a state and takes the best
Complexity = states × work per state

Memoization and Tabulation

Two implementations of the same idea, differing in direction rather than in what they compute.

Memoization is top-down. Write the natural recursion, then add a cache: on entry, return the stored value if present; on exit, store the computed one. The recursion structure is unchanged, which makes this the easier form to derive — get a correct recursive solution first, then add three lines.

Its advantages are real. It computes only the states actually reachable from the input, which on sparse problems can be a small fraction of the table. And it needs no dependency ordering — the recursion discovers what it needs when it needs it.

Its cost is the call stack. Recursion depth can reach the state-space depth, and languages with modest default limits will overflow; Python's default of 1000 frames is hit easily. Function call overhead also makes it slower by a constant factor than the equivalent loop.

Tabulation is bottom-up. Allocate the table, fill the base cases, then loop over the states in an order guaranteeing every dependency is computed before it is needed. There is no recursion and no stack risk, and the tight loops are typically faster in practice.

The catch is that you must determine the fill order yourself, and getting it wrong reads a cell before it is written — usually silently, producing an answer built on zeros. It also computes every state in the table, including unreachable ones, which wastes work on sparse problems.

Tabulation enables an optimisation memoization cannot easily match. When each row depends only on the previous row, the full table is unnecessary: keep two rows, or iterate one row in the right direction and keep just one. This rolling array takes knapsack from O(n·W) space to O(W). For the 0/1 knapsack the single-array form must iterate capacity downward, otherwise an item gets reused within the same row — and iterating upward is precisely how the unbounded knapsack is written, which is a neat illustration of how much the loop direction carries.

Memoization against tabulation
	Memoization (top-down)	Tabulation (bottom-up)
Written as	Recursion plus a cache	Loops filling a table
States computed	Only reachable ones	All of them
Ordering	Handled by the recursion	You must derive it
Stack risk	Overflow on deep states	None
Speed	Call overhead	Usually faster
Space tricks	Hard	Rolling arrays

Memoize by adding a cache to a working recursion
Tabulate by filling states in dependency order
Memoization skips unreachable states; tabulation risks no overflow
Rolling arrays cut a dimension when only the last row is needed

Key reference

Terms, operations, and practical uses

Core vocabulary

StateA set of parameters that uniquely identify a specific subproblem (e.g., index and current_capacity).
TransitionThe mathematical relationship between a state and its smaller sub-states (the recurrence relation).
MemoizationCaching the results of expensive function calls to return the cached result when the same inputs occur again (Top-Down).

Key concepts

Overlapping SubproblemsWhen a problem is broken down into subproblems which are reused several times.
Optimal SubstructureWhen an optimal solution can be constructed efficiently from optimal solutions of its subproblems.
TabulationSolving a DP problem by filling up a table (array) iteratively from the smallest subproblem up to the final answer (Bottom-Up).

Common patterns

1D DPProblems where the state can be represented by a single integer, like climbing stairs.
2D DPProblems where the state requires two integers, such as navigating a grid or comparing two strings.
KnapsackA classic pattern involving choosing items with weights and values to maximize total value within a capacity.

Implementation

Calculate Fibonacci sequence using Bottom-Up DP

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]
print(fib(5))

#include <iostream>
#include <vector>
using namespace std;
int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
int main() {
    cout << fib(5) << '\n';
}

public class Main {
    static int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println(fib(5));
    }
}

Watch it run

Step through it

Running on n = 5

Output

Read all 7 Steps

Initialize Array Create a DP array of size n+1 (6). Initialize dp[0]=0 and dp[1]=1.
Calculate fib(2) dp[2] = dp[1] + dp[0] = 1 + 0 = 1.
Calculate fib(3) dp[3] = dp[2] + dp[1] = 1 + 1 = 2.
Calculate fib(4) dp[4] = dp[3] + dp[2] = 2 + 1 = 3.
Calculate fib(5) dp[5] = dp[4] + dp[3] = 3 + 2 = 5.
Space optimization This table makes every subproblem visible. If only fib(5) were needed, two variables could replace the array because each state uses only the previous two values.
Return result The requested answer is stored at dp[5].

Recognising a DP Problem

The signals are consistent enough to act on. The problem asks for a maximum, minimum, or a count of ways — not for a specific arrangement. It involves a sequence of decisions where each affects what remains available. A greedy choice gives a wrong answer on some case you can construct. And the brute-force solution is exponential with visibly repeated work.

Counting problems are a strong tell in particular: 'how many ways' almost always sums over subproblems rather than taking a max, and rarely admits a greedy solution.

The contrast with greedy is worth keeping sharp, since they compete on similar-looking problems. Greedy commits to the locally best option and never reconsiders; it is correct only when a proof says that choice is safe. DP considers every option and keeps the best. Fractional knapsack is greedy — take the highest value-per-weight first — while 0/1 knapsack is DP, because an item cannot be split and taking the best ratio first can be wrong.

A practical route through an unfamiliar problem, in order. Write the brute-force recursion exploring all choices, ignoring efficiency. Identify which parameters actually vary across calls — that is your state. Add memoization and confirm correctness. Convert to tabulation only if the depth or the constant factor demands it, and apply a rolling array only after that works.

A few recurring families are worth recognising on sight, since most problems are variations: knapsack for subset selection under a budget, longest common subsequence for two-sequence alignment, edit distance for transformation cost, coin change for making a total from denominations, and longest increasing subsequence, which has an O(n log n) solution using binary search rather than the obvious O(n²) DP — a reminder that the first correct DP formulation is not always the intended one.

Max, min, or count of ways over a sequence of decisions
If greedy fails on a constructible case, suspect DP
Fractional knapsack is greedy; 0/1 knapsack is DP
Brute force first, then find what varies, then cache