Dynamic Programming — Remember and Reuse

Real-world analogy

What is it?

Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them into simpler overlapping subproblems, solving each subproblem just once, and storing the results for future use. It transforms exponentially slow recursive solutions into efficient polynomial-time ones.

Real-world relevance

DP is used everywhere in the real world! Google Maps uses DP to find the shortest route between cities. Spell checkers use DP (edit distance) to suggest corrections for misspelled words. Netflix uses DP-like algorithms to recommend movies you might enjoy. Even your phone's autocorrect uses Dynamic Programming to figure out what word you meant to type!

Key points

• What is Dynamic Programming? — Dynamic Programming (DP) is a technique where you break a big problem into smaller overlapping subproblems, solve each small problem once, and store the answer so you never solve it again. It is like building a house — you lay each brick once and build on top of what you already have. DP turns problems that would take forever into ones that finish in the blink of an eye!
• Overlapping Subproblems — The Key Idea — Some problems ask you to solve the same smaller problem again and again. For example, to find the 10th Fibonacci number, you need the 9th and 8th. But the 9th needs the 8th and 7th — see how the 8th gets asked twice? These repeated calculations are called overlapping subproblems. Without DP, you waste tons of time recalculating. With DP, you calculate once and remember!
• Memoization — Top-Down DP — Memoization means you start from the big problem and work your way down to smaller ones using recursion, but you store each answer in a table (like a dictionary). Before solving any subproblem, you check: did I already solve this? If yes, just return the stored answer. If no, solve it, store it, then return. It is like a student who checks their notebook before doing any calculation.
• Tabulation — Bottom-Up DP — Tabulation means you start from the smallest problems and build your way up to the big one using a loop. You fill a table from the beginning, and each entry uses previously computed entries. It is like climbing stairs — you start at step 1, then step 2, and keep going up. No recursion needed! Many competitive programmers prefer this approach because it is usually faster and avoids stack overflow.
• Fibonacci — The Classic DP Example — The Fibonacci sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21... Each number is the sum of the two before it. Without DP, computing the 40th Fibonacci number makes BILLIONS of recursive calls. With DP, it takes just 40 steps! That is the magic — DP can turn an impossibly slow solution into a lightning-fast one. Fibonacci is the hello world of Dynamic Programming.
• Top-Down vs Bottom-Up — Which is Better? — Top-down (memoization) is easier to write because it follows the natural recursive thinking. Bottom-up (tabulation) is usually faster because it avoids recursion overhead. In competitive programming, bottom-up is more common because it runs faster and uses less memory. But top-down is great when you do not need all subproblems — it only solves the ones you actually need.
• How to Spot a DP Problem — Look for these clues: the problem asks for the minimum, maximum, or count of something. The problem can be broken into smaller similar problems. Making a choice at each step affects future choices. The problem has overlapping subproblems (same calculations repeated). If you see phrases like 'find the minimum cost' or 'count the number of ways,' think DP!
• The DP Recipe — 4 Simple Steps — Step 1: Define what your DP state represents (what does dp[i] mean?). Step 2: Write the recurrence relation (how does dp[i] depend on smaller values?). Step 3: Set the base cases (what are the starting values?). Step 4: Decide the order of computation (bottom-up) or add memoization (top-down). Follow this recipe and you can solve almost any DP problem!
• Why DP Feels Hard (But Is Not!) — DP feels hard because it requires you to think about problems differently — instead of solving directly, you think about what subproblems you need. But once you practice 10-15 DP problems, patterns start to appear. Most DP problems are variations of a few classic patterns: Fibonacci-style, knapsack, grid paths, and string matching. Learn the patterns and DP becomes your superpower!

Code example

#include <bits/stdc++.h>
using namespace std;

// ===== METHOD 1: Top-Down (Memoization) =====
long long memo[51];  // Store computed Fibonacci values
bool computed[51];   // Track which values are computed

long long fibMemo(int n) {
    if (n <= 1) return n;           // Base cases: fib(0)=0, fib(1)=1
    if (computed[n]) return memo[n]; // Already solved? Return stored answer!
    
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);  // Solve and store
    computed[n] = true;
    return memo[n];
}

// ===== METHOD 2: Bottom-Up (Tabulation) =====
long long fibTab(int n) {
    if (n <= 1) return n;
    
    vector<long long> dp(n + 1);
    dp[0] = 0;  // Base case
    dp[1] = 1;  // Base case
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // Build from bottom up!
    }
    return dp[n];
}

// ===== METHOD 3: Space-Optimized Bottom-Up =====
long long fibOptimized(int n) {
    if (n <= 1) return n;
    
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        long long curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;  // Only need last two values!
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cout << "Enter n to find Fibonacci(n): ";
    cin >> n;
    
    cout << "Memoization: fib(" << n << ") = " << fibMemo(n) << "\n";
    cout << "Tabulation:  fib(" << n << ") = " << fibTab(n) << "\n";
    cout << "Optimized:   fib(" << n << ") = " << fibOptimized(n) << "\n";
    
    return 0;
}

Line-by-line walkthrough

1. 1. We create two global arrays: memo[] to store Fibonacci values and computed[] to track which ones we have already calculated. These are our 'sticky notes' for the top-down approach.
2. 2. In fibMemo(n), the base case returns n directly when n is 0 or 1. This is because fib(0) = 0 and fib(1) = 1 — the starting points of the sequence.
3. 3. Before computing, we check if computed[n] is true. If it is, we already solved this subproblem! We just return memo[n] instantly. This is the magic of memoization — no repeated work.
4. 4. If not yet computed, we recursively call fibMemo(n-1) + fibMemo(n-2), store the result in memo[n], mark computed[n] as true, and return the answer.
5. 5. In fibTab(n), we create a dp vector and fill it from the bottom up. dp[0] = 0 and dp[1] = 1 are our base cases. Then we loop from 2 to n, filling each dp[i] = dp[i-1] + dp[i-2].
6. 6. The space-optimized version fibOptimized(n) is clever — since we only ever need the last two values, we use just two variables (prev1 and prev2) instead of a whole array. This saves memory!
7. 7. In each iteration of the optimized loop, we compute curr = prev1 + prev2, then shift: prev2 becomes prev1, and prev1 becomes curr. Like a caterpillar inching forward.
8. 8. In main(), we read n and call all three methods. They all give the same answer, but use different approaches. The optimized version uses O(1) space — just two variables!
9. 9. All three methods run in O(n) time, which is incredibly fast compared to the naive recursive O(2^n). For n=50, that is the difference between instant and waiting longer than the age of the universe!

Spot the bug

#include <bits/stdc++.h>
using namespace std;

long long memo[101];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    cout << fib(0) << "\n";  // Should print 0
    cout << fib(1) << "\n";  // Should print 1
    cout << fib(2) << "\n";  // Should print 1
    cout << fib(10) << "\n"; // Should print 55
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Dynamic Programming for Beginners — Errichto (YouTube — Errichto)
• Dynamic Programming — USACO Guide (USACO Guide)
• AtCoder Educational DP Contest (AtCoder)