Without DP (naive recursion):
  Same subproblems solved MANY times  →  Exponential time

With DP (memoization or tabulation):
  Each subproblem solved ONCE         →  Polynomial time

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)   ← computed here
│   │   └── fib(1)
│   └── fib(2)       ← computed AGAIN (overlap!)
└── fib(3)           ← computed AGAIN (overlap!)
    ├── fib(2)       ← computed AGAIN (overlap!)
    └── fib(1)

Shortest path from A → D:
  A → B → C → D

  Subproblem: shortest path from B → D is also B → C → D.
  The global optimum INCLUDES the local optimum.  ✓

Longest path from A to D (without revisiting nodes):
  Subpaths may conflict — using the longest A→B path might
  prevent reaching D at all. Subproblems are NOT independent.

When does Greedy work?
  → Only when local optimum always leads to global optimum
  → Example: Activity Selection, Huffman Coding

When does DP work but Greedy fails?
  → Example: 0/1 Knapsack, Coin Change (non-canonical denominations)
  → Greedy picks heaviest items but may miss better combinations

When to use DP over plain recursion?
  → When you notice repeated subproblems in the recursion tree

Problem: Climbing stairs (how many ways to reach step n?)
State: dp[i] = number of ways to reach step i

Problem: Knapsack
State: dp[i][w] = max value using first i items with capacity w

Problem: LCS
State: dp[i][j] = length of LCS of first i chars of A and first j chars of B

Ask: "How does the current state depend on previous states?"

Climbing stairs (can take 1 or 2 steps):
  dp[i] = dp[i-1] + dp[i-2]
  (either came from step i-1 or step i-2)

House Robber (can't rob adjacent houses):
  dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  (either skip house i, or rob it and add to i-2's best)

Knapsack (item fits):
  dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i]] + val[i])
  (skip item, or take item if it fits)

// Fibonacci
dp[0] = 0;
dp[1] = 1;

// Climbing Stairs
dp[0] = 1;  // 1 way to stay at ground (do nothing)
dp[1] = 1;  // 1 way to reach step 1

// Knapsack
// dp[0][w] = 0 for all w (0 items → 0 value)
// dp[i][0] = 0 for all i (0 capacity → 0 value)

function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
// fib(40) makes ~2 billion calls!

                    fib(5)
                  /        \
             fib(4)         fib(3)
            /     \         /    \
        fib(3)  fib(2)  fib(2)  fib(1)
        /   \   /   \   /   \
     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
     /   \
  fib(1) fib(0)

Total calls: 15 for fib(5). For fib(50): ~2^50 calls.

function fib(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n] !== undefined) return memo[n];  // cache hit!
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}
// fib(40) makes only 40 unique calls

                    fib(5)
                  /        \
             fib(4)         fib(3) ← CACHED, returns immediately
            /     \
        fib(3)  fib(2) ← CACHED
        /   \
     fib(2) fib(1)
     /   \
  fib(1) fib(0)

Total unique calls: 9 for fib(5). For fib(50): exactly 50 calls.

✓ "How many ways to..." (counting problems)
✓ "Minimum/maximum cost/path/value..."
✓ "Can we achieve target X?" (feasibility)
✓ "Find the longest/shortest subsequence..."
✓ "Is there a valid partition/arrangement?"

✗ NOT DP if each subproblem is completely independent
✗ NOT DP if greedy always gives the right answer
✗ NOT DP if the problem requires actual path (BFS/DFS usually)

State: dp[a] = minimum coins needed to make amount a

For each coin c in [1, 5, 10]:
  If c <= a:
    dp[a] = min(dp[a], dp[a - c] + 1)

Interpretation: "To make amount a, try using coin c —
then we need dp[a-c] more coins for the remainder."

dp[0] = 0  (zero coins needed to make amount 0)
dp[a] = Infinity initially for all a > 0

function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;  // base case

    for (let a = 1; a <= amount; a++) {
        for (const coin of coins) {
            if (coin <= a) {
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 10], 13)); // 3 (10+2+1 or 5+5+3)
console.log(coinChange([2], 3));          // -1 (impossible)