Module 7.3 ⏱ 45 min read ⚡ Dynamic Programming Fundamentals

Dynamic Programming Fundamentals

Master memoization, tabulation, overlapping subproblems, and optimal substructure through classic problems like Fibonacci, Climbing Stairs, and 0/1 Knapsack.

1. Overlapping Subproblems & Optimal Substructure

Dynamic Programming (DP) is an algorithmic technique for solving complex problems by breaking them down into simpler overlapping subproblems. A problem exhibits optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.

Unlike divide-and-conquer strategies (where subproblems are independent), DP problems feature overlapping subproblems, meaning the same recursive states are evaluated repeatedly. Without optimization, this leads to exponential time complexities (e.g., $O(2^n)$).

2. Memoization vs. Tabulation

To eliminate redundant calculations, DP uses two primary implementation strategies:

Memoization (Top-Down): Solves the problem recursively, starting from the original target state down to base cases, while caching previously computed results in a hash map or array to ensure each subproblem is calculated only once.

Tabulation (Bottom-Up): Solves the problem iteratively by filling a lookup table from the base cases upward to the target state. Tabulation avoids recursion stack overhead and typically offers superior cache locality and execution speed.

// C++ Solution: Climbing Stairs (Tabulation Approach)
#include <vector>

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        std::vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
            

# Python Solution: Climbing Stairs (Tabulation Approach)
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]
            

// Java Solution: Climbing Stairs (Tabulation Approach)
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for computing Fibonacci numbers, solving Climbing Stairs, and optimizing the 0/1 Knapsack problem.

Quick Check: Test Your Intuition

What is the primary operational difference between Memoization and Tabulation in Dynamic Programming?