DP Implementation in C++

From Theory to Code

You've seen that dynamic programming works by breaking a big problem into smaller, overlapping subproblems. Now, let's turn that idea into actual code. There are two main ways to implement a DP solution: top-down with memoization and bottom-up with tabulation.

Think of them as two different routes to the same destination. One starts from the end and works backward, while the other starts at the beginning and works forward. Both get the job done, but one might be a more natural fit for a given problem.

The Top-Down Approach: Memoization

The top-down approach, known as memoization, feels a lot like a standard recursive solution. You write a function that calls itself to solve smaller versions of the problem. The magic ingredient is a cache, often an array or map, where you store the results of each subproblem as you solve it.

When your function is called, the first thing it does is check the cache. Has this subproblem been solved before? If yes, it returns the stored answer immediately. If not, it computes the answer, stores it in the cache for next time, and then returns it. This avoids the redundant calculations that can make plain recursion so slow.

Memoization is essentially recursion with a memory. You solve the problem by breaking it down from the top, while remembering the answers to subproblems along the way.

Let's implement this for the Fibonacci sequence, a classic DP problem. We'll use a std::vector as our cache, which we'll call memo.

#include <iostream>
#include <vector>

// Initialize memoization table with a value indicating 'not calculated yet'
std::vector<int> memo(100, -1); 

int fib(int n) {
    // Base cases
    if (n <= 1) {
        return n;
    }

    // Check if the value is already computed
    if (memo[n] != -1) {
        return memo[n];
    }

    // Compute and store the result if not already done
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") = " << fib(n) << std::endl; // Output: 55
    return 0;
}

The structure of the fib function directly follows the recursive definition of Fibonacci numbers ( $F_n = F_{n-1} + F_{n-2}$ ). The memo vector prevents us from re-computing the same Fibonacci number over and over. Because we only solve the subproblems that are actually needed to reach our target n, this approach can be very efficient if only a fraction of all possible subproblems are relevant.

The Bottom-Up Approach: Tabulation

Tabulation takes the opposite approach. It's an iterative method that starts with the smallest, most basic subproblems and solves them first. It fills a table (hence the name) from the bottom up, using the results of solved subproblems to figure out the next, larger ones.

This process continues until you've built up the solution to the original, top-level problem. There's no recursion involved, which means you avoid the risk of a stack overflow for very deep recursion. The logic can sometimes feel less intuitive than memoization because you have to figure out the correct order to solve the subproblems in.

Tabulation builds the solution from the ground up. You solve all the foundational subproblems first and use their results to construct the final answer.

Here's how we would solve the Fibonacci problem using tabulation. We create a table, dp, to store the Fibonacci numbers in order.

#include <iostream>
#include <vector>

int fib(int n) {
    if (n <= 1) {
        return n;
    }

    // Create a table to store results
    std::vector<int> dp(n + 1);

    // Initialize base cases
    dp[0] = 0;
    dp[1] = 1;

    // Fill the table from the bottom up
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") = " << fib(n) << std::endl; // Output: 55
    return 0;
}

This code directly calculates each Fibonacci number starting from dp[2] and stores it. Each calculation, dp[i], only depends on the two preceding values, dp[i-1] and dp[i-2], which we've already solved. It's a straightforward loop that guarantees every subproblem is solved exactly once.

Choosing Your Strategy

So, which approach is better? It depends on the problem and your personal preference. Neither is universally superior.

Feature	Memoization (Top-Down)	Tabulation (Bottom-Up)
Logic	Recursive, often mirrors the problem definition directly.	Iterative, requires thinking about the order of subproblems.
Subproblems Solved	Only solves subproblems that are necessary for the target solution.	Solves all subproblems up to the target solution.
Overhead	Can have function call overhead from recursion.	No recursion overhead, can be slightly faster.
Stack Space	Might cause a stack overflow for very deep recursion.	Not susceptible to stack overflow errors.
Implementation	Can be easier to write if you already have a recursive solution.	Can be more complex to set up the iteration correctly.

Memoization is often a good starting point because it's a natural extension of a pure recursive solution. If the problem space is vast and you only need to solve a sparse subset of subproblems, memoization shines. Tabulation is a great choice when you need to solve all subproblems anyway, or when you're worried about recursion depth. With tabulation, you can also sometimes optimize space by realizing you only need the last few results, not the entire table.

Quiz Questions 1/5

What is the fundamental difference between the top-down (memoization) and bottom-up (tabulation) approaches to dynamic programming?

Quiz Questions 2/5

In the context of dynamic programming, what is the primary role of the cache (e.g., a memo array or map) in a memoization-based solution?

Mastering Dynamic Programming