Dynamic Programming | DSA Mastery

DP is an optimization technique that solves complex problems by breaking them into overlapping subproblems and storing results to avoid recomputation. Two key properties: Optimal Substructure + Overlapping Subproblems. Made famous by Richard Bellman in the 1950s.

🔄 Two DP Approaches

1️⃣ Top-Down (Memoization)

Start with original problem, recursively solve subproblems, cache results in a map/array. First time solving a subproblem = compute & store. Next time = return cached.

function fib(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fib($n-1,$memo) + fib($n-2,$memo);
} // O(n) time, O(n) space

2️⃣ Bottom-Up (Tabulation)

Start from smallest subproblems, iteratively build up to the answer. Fill a table (array) in order. Usually more efficient (no recursion overhead).

function fib(int $n): int {
    if ($n <= 1) return $n;
    $dp = [0, 1];
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = $dp[$i-1] + $dp[$i-2];
    }
    return $dp[$n];
} // O(n) time, O(n) space
// Space optimized: O(1) - only keep last 2

🧠 When to Use DP?

Recognition Checklist:

Optimization problem? (minimize, maximize, count ways)
Optimal substructure? (solution built from subproblem solutions)
Overlapping subproblems? (same subproblem solved multiple times)
Can't be solved greedily? (future decisions depend on past choices)

Keywords in problems: "minimum", "maximum", "number of ways", "longest", "shortest", "can be partitioned"

📝 5-Step DP Framework

💡 Classic Example: 0/1 Knapsack

// Bottom-Up DP - O(n*W) time, O(n*W) space
function knapsack01(array $weights, array $values, int $capacity): int {
    $n = count($weights);
    // dp[i][w] = max value for first i items, capacity w
    $dp = array_fill(0, $n+1, array_fill(0, $capacity+1, 0));

    for ($i = 1; $i <= $n; $i++) {
        for ($w = 0; $w <= $capacity; $w++) {
            if ($weights[$i-1] <= $w) {
                // Max of: skip item i  OR  take item i
                $dp[$i][$w] = max(
                    $dp[$i-1][$w],
                    $dp[$i-1][$w - $weights[$i-1]] + $values[$i-1]
                );
            } else {
                $dp[$i][$w] = $dp[$i-1][$w]; // Can't take
            }
        }
    }
    return $dp[$n][$capacity];
}

// Test
$weights = [2, 3, 4, 5]; $values = [3, 4, 5, 6];
echo knapsack01($weights, $values, 8); // 10 (items 2+3 or 1+4)

🎯 Common DP Patterns

1D DP	Fibonacci, Climbing Stairs, House Robber, Coin Change	dp[i] depends on dp[i-1], dp[i-2]...
2D DP	Knapsack, LCS, Edit Distance, Subset Sum	dp[i][j] grid, often O(n*m)
DP on Strings	LCS, Edit Distance, Palindrome Partitioning	2D table, compare characters
DP on Intervals	Matrix Chain, Burst Balloons	dp[i][j] = best for subarray i..j
DP with Bitmask	TSP, Assignment Problem	dp[mask][i], mask = visited set
DP on Trees	Tree DP, Diameter, Max Path Sum	Postorder traversal + DP
DP on Grid	Unique Paths, Min Path Sum	dp[i][j] from dp[i-1][j], dp[i][j-1]

⚡ DP Optimizations

👉 See detailed implementations for 15 DP problems in the DP Problems section.

📊 Dynamic Programming

🎯 What is Dynamic Programming?