DP Time = Number of Unique States × Average Work per State Transition
DP Space = Number of Unique States (for the DP table)

// Example: Coin Change
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    //         └──── states = amount + 1  (0..amount)
    dp[0] = 0;

    for (let a = 1; a <= amount; a++) {       // Outer: iterate all states
        for (const coin of coins) {            // Inner: work per state = O(coins)
            if (coin <= a) {
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
    }
    // Total = O(states × work) = O(amount × coins)
    return dp[amount];
}

// Before: O(n) space
const dp = new Array(n + 1);
dp[0] = 0; dp[1] = 1;
for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];

// After: O(1) space
let a = 0, b = 1;
for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
}
return b;

// Before: O(m × n) space
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        dp[i][j] = recurrence(dp[i-1][j], dp[i][j-1], ...);
    }
}
return dp[m][n];

// After: O(n) space (two rows)
let prev = new Array(n + 1).fill(0);
let curr = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        curr[j] = recurrence(prev[j], curr[j-1], prev[j-1]);
    }
    [prev, curr] = [curr, prev];  // swap rows
}
return prev[n];

// Knapsack: O(W) space by iterating W backwards
const dp = new Array(W + 1).fill(0);
for (const item of items) {
    for (let w = W; w >= item.weight; w--) {  // ← backward!
        dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value);
    }
}
return dp[W];

0/1 Knapsack:   O(n × W)
  - n = number of items (input size)
  - W = capacity (numerical value)
  - If W is represented in k bits, W can be up to 2^k
  - So O(n × W) = O(n × 2^k) = EXPONENTIAL in terms of bit length!
  - This is called "pseudo-polynomial" time

Subset Sum:     O(n × target)
  - Same issue — target can be exponential in bit representation

DP is NOT suitable when:
❌ Subproblems are independent (use divide & conquer)
❌ Greedy works (use greedy — it's faster)
❌ The state space is huge (use approximation)
❌ W or target sum is astronomically large (pseudo-polynomial explosion)
❌ Input size is very small (O(n²) DP may be overkill)

           Original      Optimized    Technique
           ────────      ────────     ─────────
Fibonacci    O(n)          O(1)       Rolling variables
Climbing Stairs O(n)       O(1)       Rolling variables
House Robber  O(n)         O(1)       Rolling variables
LCS          O(m×n)       O(n)        Two rows
Edit Distance O(m×n)      O(n)        Two rows
Unique Paths O(m×n)       O(n)        1D array
Knapsack     O(n×W)       O(W)        1D backward
LPS          O(n²)        O(n)        Two rows
Subset Sum   O(n×T)       O(T)        1D backward

1D DP (single state variable)
├── Time usually: O(n) or O(n²)
├── Space usually: O(n) → O(1) possible
└── Examples: Fibonacci, Stairs, Robber, Coin Change

2D DP (two state variables)
├── Time usually: O(n×m) or O(n²) or O(n³)
├── Space usually: O(n×m) → O(m) or O(n) possible
└── Examples: LCS, Knapsack, Edit Distance, Grid DP

3D DP (three state variables — rare)
├── Time usually: O(n³) or higher
├── Space usually: O(n²) or O(n³)
└── Examples: Egg Dropping, Burst Balloons (interval dp)

FORMULA:
  Time  = (number of states) × (work per state transition)
  Space = size of DP table (before optimization)

RULES OF THUMB:
  n = length of input array/string
  k = number of choices at each state
  W = knapsack capacity
  T = target sum

  Iterating array once:     O(n), O(1) space
  Nested loop over array:   O(n²), O(n²) space → O(n) optimized
  Triple nested loop:       O(n³), O(n²) space → O(n²) optimized
  Loop over capacity:       pseudo-polynomial O(n×W) or O(n×T)

SPACE OPTIMIZATION:
  dp[i] depends on dp[i-1], dp[i-2]        → O(1) rolling variables
  dp[i][j] depends on previous row only    → O(n) two rows
  dp[i][w] depends on prev row + smaller w → O(W) single array (backwards)
  Need entire table for reconstruction     → Cannot optimize space