I've always found that the term "Dynamic Programming" sounds far more intimidating than it actually is. In reality, it's just a fancy way of saying, "I'm tired of calculating the same thing twice, so I'm going to write the answer down."

Let's look at a classic problem: the Longest Common Subsequence (LCS). Given two strings, we want to find the length of the longest sequence of characters that appear in both, in the same relative order (but not necessarily consecutively). For example, "ABCDE" and "ACE" have an LCS of "ACE", length 3.

The Recursive Trap

My first instinct is usually to write a recursive function. It's the most natural way to express the logic: if the last characters match, we count it and move back. If they don't, we try skipping a character from either string and see which path yields a better result. Here is how that looks in C++:

int lcs(std::string s1, std::string s2, int m, int n) {
    if (m == 0 || n == 0) return 0;
    if (s1[m-1] == s2[n-1]) {
        return 1 + lcs(s1, s2, m-1, n-1);
    } else {
        return std::max(lcs(s1, s2, m, n-1), lcs(s1, s2, m-1, n));
    }
}

This feels elegant, right? But let's try running this with strings of length 20 or 30. Suddenly, the program hangs. Why? Because we're creating a massive recursion tree. If the characters don't match, we branch twice. For strings of length $N$ and $M$, we're looking at an exponential time complexity of $O(2^{N+M})$. I'm effectively recalculating the LCS for the same suffixes thousands of times.

Plugging the Leaks with Memoization

I don't want to throw away the recursive logic—it's intuitive. Instead, I'll add a "notebook" to store results we've already found. In C++, a 2D vector is perfect for this. I'll initialize it with -1 to indicate that a specific sub-problem hasn't been solved yet.

int memo[101][101]; // Assuming max length 100

int lcs_memo(std::string& s1, std::string& s2, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    // Check if we already have the answer
    if (memo[m][n] != -1) return memo[m][n];

    if (s1[m-1] == s2[n-1]) {
        return memo[m][n] = 1 + lcs_memo(s1, s2, m-1, n-1);
    } else {
        return memo[m][n] = std::max(lcs_memo(s1, s2, m, n-1), 
                                     lcs_memo(s1, s2, m-1, n));
    }
}

Now, the performance is night and day. We've shifted from exponential time to $O(M \times N)$. This is "Top-Down" DP. We start with the big problem and break it down, caching as we go. It's great, but it still carries the overhead of the function call stack. If our strings were thousands of characters long, we'd hit a stack overflow.

Turning the Table

To avoid the stack entirely, I can flip the logic. Instead of starting at the end and going backward, I'll start at the beginning and build a table upward. This is "Bottom-Up" DP (Tabulation).

I need a 2D table where dp[i][j] represents the LCS of s1[0...i-1] and s2[0...j-1]. I'll fill it row by row. The logic remains the same, but now it's just nested loops.

int lcs_tabulated(std::string s1, std::string s2) {
    int m = s1.size();
    int n = s2.size();
    std::vector> dp(m + 1, std::vector(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

Notice what happened here. The "pattern" of DP is essentially identifying the dependency. To calculate dp[i][j], I only ever need the cell to the left, the cell above, and the cell diagonally up-left. This realization is powerful because it tells me I don't actually need the whole 2D table—I only need the current row and the previous row. If I were optimizing for memory in a production system, I'd swap that vector> for two simple vector arrays.

📋 Practical Task

Implement a Levenshtein Distance Calculator

The Levenshtein Distance (or Edit Distance) is a close cousin of the LCS problem. It measures how many single-character edits (insertions, deletions, or substitutions) are required to change one word into another. This is the core logic behind most "Did you mean...?" spell-checkers.

Your Task: Write a C++ function int editDistance(std::string s1, std::string s2) using a bottom-up DP approach (tabulation).

The Logic Rules:

• If the characters at the current position match, the cost is 0 (just move to the next characters).
• If they don't match, you must take the minimum of three possible operations:
  1. Insert: 1 + dp[i][j-1]
  2. Delete: 1 + dp[i-1][j]
  3. Substitute: 1 + dp[i-1][j-1]
• Base cases: If one string is empty, the distance is the length of the other string (all insertions or all deletions).

Test your implementation with "kitten" and "sitting" (the result should be 3: substitute 'k' for 's', substitute 'e' for 'i', and add 'g' at the end).