Dynamic Programming

Core Concepts

Memoization (Top-Down): Using recursion and caching the results of expensive function calls.
Tabulation (Bottom-Up): Building a table (array) iteratively to solve subproblems from smallest to largest.

graph TD A["Fib(4)"] --> B["Fib(3)"] A --> C["Fib(2)"] B --> D["Fib(2)"] B --> E["Fib(1)"] C -.-> |"Cached!"| F["O(1)"]

Cheatsheet Formulas

Top-Down (Memoization): memo = {}. def dp(state): if state in memo: return memo[state]; result = ...; memo[state] = result; return result.
Bottom-Up (Tabulation): dp = [0] * (N+1). dp[0] = base_case. Loop i from 1 to N: dp[i] = dp[i-1] + ....
Knapsack (0/1): dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]).

Classic Problem: Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int first = 1;
        int second = 2;
        
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        
        return second;
    }
}

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
            
        first, second = 1, 2
        
        for _ in range(3, n + 1):
            first, second = second, first + second
            
        return second