Dynamic Programming

# CHAPTER 29

Dynamic Programming (Memoization & Tabulation) #

1. Introduction #

2. Learning Objectives #

• Identify the "Overlapping Subproblems" vulnerability in basic recursion.

• Implement Top-Down Dynamic Programming (Memoization).

• Implement Bottom-Up Dynamic Programming (Tabulation).

• Dramatically reduce O(2^n) exponential time complexities to O(n) linear time.

3. The Problem: The Recursive Nightmare #

# A standard, naive Recursive function
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

If we call fib(5), it branches out to calculate fib(4) and fib(3). But fib(4) *also* branches out to calculate fib(3) and fib(2). The CPU ends up calculating fib(3) multiple times! It calculates fib(2) dozens of times! This redundant recalculation causes a catastrophic O(2^n) Exponential Time Complexity. Calculating fib(50) using this naive code will physically lock up your computer for years because it attempts to execute quadrillions of redundant recursive branches.

4. Method 1: Memoization (Top-Down DP) #

// Java Example: Top-Down Memoization
import java.util.HashMap;

public class DPExample {
    // The Cache! Maps the 'n' value to the previously calculated answer
    HashMap<Integer, Long> memo = new HashMap<>();

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

        // 1. Check the Cache BEFORE doing any math!
        if (memo.containsKey(n)) {
            return memo.get(n); // Instant O(1) return!
        }

        // 2. Heavy calculation required.
        long result = fib(n - 1) + fib(n - 2);

        // 3. SAVE THE ANSWER for the future!
        memo.put(n, result);

        return result;
    }
}

The Result: fib(50) now executes in mere milliseconds. We collapsed an impossible O(2^n) time complexity down to a flawless O(n) Linear Time!

5. Method 2: Tabulation (Bottom-Up DP) #

// C++ Example: Bottom-Up Tabulation
#include <iostream>
#include <vector>

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

    // 1. Create a physical Array table to hold all answers up to n
    std::vector<long long> dp(n + 1);

    // 2. Hardcode the absolute base cases at the bottom
    dp[0] = 0;
    dp[1] = 1;

    // 3. Iteratively loop UPWARD to build the answers!
    for (int i = 2; i <= n; i++) {
        // Look backwards into the table to calculate the current slot
        dp[i] = dp[i - 1] + dp[i - 2]; 
    }

    // 4. The final answer is sitting comfortably at the end of the table
    return dp[n]; 
}

The Result: O(n) Time Complexity, and NO recursion crashes!

6. The Core Principles of DP #

1. 1. Overlapping Subproblems: The exact same smaller calculations are repeated multiple times (like fib(3)).

1. 2. Optimal Substructure: The optimal solution to the massive, overarching problem can be perfectly constructed from the optimal solutions of its smaller subproblems.

7. Space Complexity Optimization #

# Python Example: Ultimate O(1) Space DP
def fib_optimized(n):
    if n <= 1: return n
    
    a, b = 0, 1 # Track the two previous numbers
    for _ in range(2, n + 1):
        next_val = a + b
        a = b
        b = next_val
        
    return b

8. Common DP Interview Questions #

1. 1. The Climbing Stairs Problem: You can climb 1 step or 2 steps. How many distinct ways can you reach the top of an N-step staircase? *(Hint: It's secretly just the Fibonacci sequence!).*

1. 2. The 0/1 Knapsack Problem: A thief has a backpack that holds W pounds. Given an array of items with different weights and values, maximize the value stolen without breaking the backpack.

1. 3. Longest Common Subsequence: Given two strings "abcde" and "ace", find the length of the longest identical sequence of letters.

9. Common Mistakes #

• Applying DP blindly: Junior devs will sometimes try to Memoize algorithms like Merge Sort. Merge Sort slices arrays into entirely unique halves. The left half has absolutely nothing in common with the right half. Because there are no *Overlapping Subproblems*, a Cache is completely useless and just wastes RAM!

10. Exercises #

1. 1. Draw a recursive branching diagram for the naive fib(4). Count exactly how many times the function fib(2) is explicitly evaluated by the CPU.

1. 2. In the Tabulation for loop algorithm, why does it absolutely guarantee that no OS Call Stack Overflow crashes will occur?

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Coding:* "House Robber Problem: You are a thief. You can rob houses sequentially down a street, but you cannot rob two *adjacent* houses without triggering an alarm. Given an array of house cash values, maximize your steal." *(Answer: The ultimate 1D DP array problem. At every house i, you must mathematically choose the maximum between: The cash at house [i-1] OR the cash at house [i-2] + current house cash).*

13. FAQs #

14. Summary #

15. Next Chapter Recommendation #