Don't solve it twice
Naive recursive Fibonacci recomputes the same values millions of times. Dynamic programming (DP) saves each subproblem's answer — top-down with a memo, or bottom-up with a table — turning exponential time into polynomial. It solves what greedy can't, like fewest coins for any coin set.
Memo vs table
let calls = 0;
function slowFib(n) { calls++; return n < 2 ? n : slowFib(n - 1) + slowFib(n - 2); }
slowFib(25);
console.log("naive calls:", calls);
function memoFib(n, memo = new Map()) {
if (n < 2) return n;
if (memo.has(n)) return memo.get(n);
const v = memoFib(n - 1, memo) + memoFib(n - 2, memo);
memo.set(n, v);
return v;
}
console.log(memoFib(90));
// Fewest coins (greedy fails for [25, 10, 1] and 30).
function minCoins(amount, coins) {
const best = new Array(amount + 1).fill(Infinity);
best[0] = 0;
for (let a = 1; a <= amount; a++)
for (const c of coins)
if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
return best[amount] === Infinity ? -1 : best[amount];
}
console.log(minCoins(30, [25, 10, 1]), minCoins(7, [2, 4]));- 1. Define the state (what does dp[i] mean?).
- 2. Write the recurrence from smaller states.
- 3. Set base cases.
- 4. Fill in an order where dependencies come first.