Dynamic Programming

// 1) Fibonacci — the canonical example
// Naive: O(2^n)
function fib(n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

// Top-down with memo: O(n)
const memo = new Map();
function fibMemo(n) {
    if (n < 2) return n;
    if (memo.has(n)) return memo.get(n);
    const v = fibMemo(n - 1) + fibMemo(n - 2);
    memo.set(n, v);
    return v;
}

// Bottom-up table: O(n) time, O(1) space
function fibTab(n) {
    let a = 0, b = 1;
    for (let i = 0; i < n; i++) [a, b] = [b, a + b];
    return a;
}

// 2) Climbing stairs — distinct ways to reach step n
function climbStairs(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = dp[1] = 1;
    for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

// 3) Coin change — fewest coins to make amount
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let a = 1; a <= amount; a++) {
        for (const c of coins) {
            if (a - c >= 0) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// 4) Longest increasing subsequence
function lis(nums) {
    const dp = new Array(nums.length).fill(1);
    let max = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

// 5) Knapsack (0/1) — pick items to maximise value within capacity
function knapsack(weights, values, capacity) {
    const dp = new Array(capacity + 1).fill(0);
    for (let i = 0; i < weights.length; i++) {
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

// 6) Edit distance — Levenshtein
function editDistance(a, b) {
    const m = a.length, n = b.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        }
    }
    return dp[m][n];
}

// 7) When to use DP — three signs
//   • The recursion has overlapping subproblems (same inputs visited > once)
//   • Optimal substructure (best answer = combine best sub-answers)
//   • State space is countable and bounded

// 8) Decision template
//   - Identify state (the args to the recursive call)
//   - Identify transitions (how this state depends on smaller ones)
//   - Establish base cases
//   - Memoise OR build a table
//   - Space-optimise if rows only depend on the previous row

// 9) Python — @cache for one-liner memoisation
# from functools import cache
# @cache
# def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)

// Climbing stairs (1 or 2 steps). dp[i] = dp[i-1] + dp[i-2].
function climb(n) {
    let a = 1, b = 1;
    for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
    return b;
}