DP 1. Introduction to Dynamic Programming | Memoization | Tabulation | Space Optimization Techniques

Dynamic Programming (DP) is one of the most crucial problem-solving paradigms in computer science and technical interviews. This chapter introduces the core principles of dynamic programming, breaking down how to transform inefficient recursive solutions into highly optimized iterative and space-efficient algorithms using the canonical Fibonacci sequence as our foundational mental model.

1. Why Do We Need Dynamic Programming? (The Status Quo)

When solving complex computational problems, standard recursive approaches often explore the exact same sub-problems repeatedly. This leads to exponential time complexities ($O(2^n)$), making the program freeze or crash for moderately large inputs.

Dynamic Programming steps in as an optimization technique designed to solve problems with overlapping sub-problems by storing results of intermediate states. Instead of recalculating past results, we remember them.

Famous Quote: "Those who cannot remember the past are condemned to repeat it."

2. The Core Mental Model: The Fibonacci Sequence

To understand the mechanics of Dynamic Programming, we examine the Fibonacci number generator.

Sequence Definition

• The 0th Fibonacci number is 0.
• The 1st Fibonacci number is 1.
• Every subsequent number is the sum of the preceding two numbers.

Index:     0, 1, 2, 3, 4, 5,  6,  7,  8, ...
Fibonacci: 0, 1, 1, 2, 3, 5,  8, 13, 21, ...

Recurrence Relation

To find the $n$-th Fibonacci number ($F(n)$), we define our recursive relation:

Naive Recursion Code

int f(int n) {
    if (n <= 1) return n;
    return f(n - 1) + f(n - 2);
}

• Time Complexity: $O(2^n)$ (Exponential due to duplicate branch evaluations).
• Space Complexity: $O(n)$ (Call stack depth).

3. The Anatomy of Overlapping Sub-Problems

If we evaluate $F(5)$ using naive recursion, the function calls branch out into a massive tree structure.

                    f(5)
                   /    \
               f(4)      f(3)
              /    \     /    \
          f(3)    f(2) f(2)   f(1)
         /    \
     f(2)    f(1)

Notice how f(3) and f(2) are evaluated multiple times across different branches. This redundancy is known as Overlapping Sub-Problems. Once $F(2)$ is computed the first time, its value will never change; thus, recomputing it is a waste of CPU cycles.

4. Approach 1: Memoization (Top-Down Dynamic Programming)

Memoization is the technique of caching the results of sub-problems the first time they are solved, so subsequent requests can retrieve the answer in $O(1)$ constant time.

• Top-Down Definition: We start from the target problem ($n$) and recursively break it down toward the base cases ($0$ and $1$), storing results along the way.

The 3-Step Memoization Blueprint

1. Step 0 (Declare DP Array): Create a lookup structure (e.g., an array or vector) of size $n + 1$ initialized with -1 to represent uncomputed states.
2. Step 1 (Store Computed Answers): Whenever a sub-problem's result is calculated, store it in the DP array before returning.
3. Step 2 (Check Before Computing): At the beginning of the function, check if the sub-problem's value is already computed (i.e., not equal to -1). If so, return it immediately.

C++ Memoization Implementation

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

int fib(int n, vector<int>& dp) {
    // Base case
    if (n <= 1) return n;
    
    // Step 2: Check if already computed
    if (dp[n] != -1) return dp[n];
    
    // Step 1: Compute, store, and return
    return dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
}

int main() {
    int n = 5;
    vector<int> dp(n + 1, -1);
    cout << fib(n, dp) << endl; // Output: 5
    return 0;
}

• Time Complexity: $O(n)$ (Each sub-problem is solved exactly once).
• Space Complexity: $O(n)$ (DP array storage + Recursion stack space).

5. Approach 2: Tabulation (Bottom-Up Dynamic Programming)

While memoization is top-down, Tabulation is bottom-up. We start directly from the base cases and iteratively build up our table to reach the target $n$.

The 3-Step Tabulation Blueprint

1. Declare a DP array of size $n + 1$.
2. Initialize the base cases directly into the DP array (e.g., dp[0] = 0, dp[1] = 1).
3. Run a loop from 2 up to n, filling in the table using the recurrence relation.

C++ Tabulation Implementation

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

int main() {
    int n = 5;
    if (n <= 1) {
        cout << n << endl;
        return 0;
    }

    vector<int> dp(n + 1);
    
    // Step 2: Initialize base cases
    dp[0] = 0;
    dp[1] = 1;
    
    // Step 3: Iterative bottom-up filling
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    cout << dp[n] << endl; // Output: 5
    return 0;
}

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$ (Eliminates recursion stack space, but still retains the DP array).

6. Approach 3: Space Optimization Techniques

Can we do even better? Look closely at the tabulation recurrence:

To compute the current value, we only ever need the previous two values (i-1 and i-2). We do not need an entire array spanning all $n$ elements!

The Rolling Variable Mental Model

Instead of a full array, we maintain two tracking variables:

• prev: Represents $F(i-1)$
• prev2: Represents $F(i-2)$

As our loop iterates forward, we shift our variables:

Iteration Start:   [prev2] [prev] [current]
Shift Forward:             [prev2]  [prev]  [current (calculated)]

C++ Space-Optimized Implementation

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

int main() {
    int n = 5;
    if (n <= 1) {
        cout << n << endl;
        return 0;
    }

    int prev2 = 0; // Represents F(0)
    int prev = 1;  // Represents F(1)
    int curr = 0;

    for (int i = 2; i <= n; i++) {
        curr = prev + prev2; // Current fibonacci number
        prev2 = prev;        // Shift prev2 forward
        prev = curr;         // Shift prev forward
    }

    cout << prev << endl; // Output: 5
    return 0;
}

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$ (Optimal constant space).

7. Comparative Synthesis of DP Strategies

The following table summarizes the evolution of strategies covered in this chapter, highlighting how time and space efficiencies improve across iterations:

Summary and Key Takeaways

• Dynamic Programming Definition: An optimization technique that solves problems by breaking them down into simpler sub-problems and storing results to avoid redundant calculations.
• Overlapping Sub-Problems: The core condition where the same recursive sub-problems are evaluated multiple times, creating the necessity for caching.
• Memoization (Top-Down): Caching recursive results using a lookup array (dp) combined with base checks to achieve linear time complexity.
• Tabulation (Bottom-Up): Iteratively building solutions from base cases upwards, completely eliminating recursion stack overhead.
• Space Optimization: Recognizing that most DP problems only depend on a fixed number of prior states (e.g., i-1 and i-2), allowing us to reduce space complexity from $O(n)$ down to $O(1)$.
• The 3-Step Conversion Framework:
  1. Write the correct brute-force recursion.
  2. Apply memoization (Check cache $\rightarrow$ Compute $\rightarrow$ Store in cache).
  3. Convert to tabulation and apply space optimization variables.
• Interview Standard: Delivering the space-optimized solution ($O(n)$ time, $O(1)$ space) demonstrates elite coding proficiency and guarantees strong evaluation marks.