Memoization vs Tabulation — The 10000-Stack-Frame Gotcha

import java.util.HashMap;
import java.util.Map;

public class MemoizationFibonacci {

    // Cache stores results we've already computed
    // Key = the nth position, Value = the Fibonacci number at that position
    private static Map<Integer, Long> cache = new HashMap<>();

    public static long fibonacci(int n) {
        // Base cases — the foundation every recursive call eventually hits
        if (n <= 1) return n;

        // Check the cache BEFORE doing any work
        // If we've solved fib(n) before, return the stored answer immediately
        if (cache.containsKey(n)) {
            System.out.println("  Cache hit for fib(" + n + ") = " + cache.get(n));
            return cache.get(n);
        }

        // We haven't solved this subproblem yet — compute it recursively
        long result = fibonacci(n - 1) + fibonacci(n - 2);

        // Store the result so future calls don't recompute it
        cache.put(n, result);
        System.out.println("  Computed and cached fib(" + n + ") = " + result);

        return result;
    }

    public static void main(String[] args) {
        System.out.println("--- Computing fibonacci(7) with memoization ---");
        long answer = fibonacci(7);
        System.out.println("\nfibonacci(7) = " + answer);

        System.out.println("\n--- Computing fibonacci(9) — notice cache hits for values already known ---");
        long answer2 = fibonacci(9);
        System.out.println("\nfibonacci(9) = " + answer2);
    }
}

public class TabulationFibonacci {

    public static long fibonacci(int n) {
        // Handle edge cases before building the table
        if (n <= 1) return n;

        // The DP table — index i holds the Fibonacci number at position i
        // We allocate exactly n+1 slots to cover positions 0 through n
        long[] dpTable = new long[n + 1];

        // Seed the table with our known base cases
        dpTable[0] = 0;  // fib(0) = 0
        dpTable[1] = 1;  // fib(1) = 1

        System.out.println("Building the DP table bottom-up:");
        System.out.printf("  dpTable[0] = %d (base case)%n", dpTable[0]);
        System.out.printf("  dpTable[1] = %d (base case)%n", dpTable[1]);

        // Fill every cell from 2 to n in order
        // Each cell depends ONLY on previously filled cells — no recursion needed
        for (int position = 2; position <= n; position++) {
            dpTable[position] = dpTable[position - 1] + dpTable[position - 2];
            System.out.printf("  dpTable[%d] = dpTable[%d] + dpTable[%d] = %d + %d = %d%n",
                position,
                position - 1,
                position - 2,
                dpTable[position - 1],
                dpTable[position - 2],
                dpTable[position]);
        }

        // The answer is sitting right in the last cell we filled
        return dpTable[n];
    }

    // BONUS: Space-optimized version — we only ever need the last two values
    // This drops memory from O(n) to O(1)
    public static long fibonacciSpaceOptimized(int n) {
        if (n <= 1) return n;

        long previousPrevious = 0;  // Represents fib(i-2)
        long previous = 1;          // Represents fib(i-1)
        long current = 0;

        for (int position = 2; position <= n; position++) {
            current = previous + previousPrevious;
            previousPrevious = previous;  // Slide the window forward
            previous = current;
        }
        return current;
    }

    public static void main(String[] args) {
        System.out.println("=== Tabulation (full table) ===");
        long answer = fibonacci(7);
        System.out.println("\nfibonacci(7) = " + answer);

        System.out.println("\n=== Space-Optimized Tabulation (O(1) space) ===");
        long optimizedAnswer = fibonacciSpaceOptimized(7);
        System.out.println("fibonacci(7) = " + optimizedAnswer);
    }
}

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CoinChangeBothApproaches {

    // ─────────────────────────────────────────
    // APPROACH 1: MEMOIZATION (Top-Down)
    // ─────────────────────────────────────────
    private static Map<Integer, Integer> memo = new HashMap<>();

    public static int minCoinsMemo(int[] coinDenominations, int remainingAmount) {
        // Base case: no amount left means zero coins needed
        if (remainingAmount == 0) return 0;

        // Base case: negative amount means this coin path is invalid
        if (remainingAmount < 0) return Integer.MAX_VALUE;

        // Return cached result if we've already solved this subproblem
        if (memo.containsKey(remainingAmount)) return memo.get(remainingAmount);

        int fewestCoins = Integer.MAX_VALUE;

        // Try every coin and pick the path that uses the fewest coins overall
        for (int coin : coinDenominations) {
            int subResult = minCoinsMemo(coinDenominations, remainingAmount - coin);

            // Only update if the subproblem was solvable (not MAX_VALUE)
            // and adding 1 coin to it doesn't overflow
            if (subResult != Integer.MAX_VALUE) {
                fewestCoins = Math.min(fewestCoins, 1 + subResult);
            }
        }

        memo.put(remainingAmount, fewestCoins);
        return fewestCoins;
    }

    // ─────────────────────────────────────────
    // APPROACH 2: TABULATION (Bottom-Up)
    // ─────────────────────────────────────────
    public static int minCoinsTabulation(int[] coinDenominations, int targetAmount) {
        // dpTable[amount] = minimum coins needed to make 'amount'
        // Initialize everything to targetAmount+1 (a value larger than any real answer)
        // We use targetAmount+1 instead of Integer.MAX_VALUE to safely do +1 arithmetic
        int[] dpTable = new int[targetAmount + 1];
        Arrays.fill(dpTable, targetAmount + 1);

        // Base case: zero coins needed to make amount 0
        dpTable[0] = 0;

        // Fill the table for every amount from 1 up to targetAmount
        for (int currentAmount = 1; currentAmount <= targetAmount; currentAmount++) {
            for (int coin : coinDenominations) {
                // Only consider this coin if it doesn't exceed the current amount
                if (coin <= currentAmount) {
                    // Either keep what we have, or use this coin + whatever it takes
                    // to make (currentAmount - coin)
                    dpTable[currentAmount] = Math.min(
                        dpTable[currentAmount],
                        1 + dpTable[currentAmount - coin]
                    );
                }
            }
        }

        // If the value is still the sentinel, the amount is impossible to make
        return dpTable[targetAmount] > targetAmount ? -1 : dpTable[targetAmount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 6, 9};
        int target = 11;

        System.out.println("Coin denominations: " + Arrays.toString(coins));
        System.out.println("Target amount: " + target);

        // Reset memo before running (important if reusing across calls)
        memo.clear();
        int memoResult = minCoinsMemo(coins, target);
        System.out.println("\nMemoization result: " + memoResult + " coins");
        // Optimal: 9 + 1 + 1 = 3 coins, or 6 + 5 = 2 coins — answer is 2

        int tabulationResult = minCoinsTabulation(coins, target);
        System.out.println("Tabulation result:  " + tabulationResult + " coins");

        // Test an impossible case
        int[] coinsNoOne = {3, 7};
        int impossibleTarget = 5;
        System.out.println("\nCoins: " + Arrays.toString(coinsNoOne) + ", Target: " + impossibleTarget);
        System.out.println("Tabulation result for impossible case: " + minCoinsTabulation(coinsNoOne, impossibleTarget));
    }
}

package io.thecodeforge;

public class KnapsackSpaceOptimized {

    // 0/1 Knapsack with space-optimized tabulation
    // dp[capacity] stores max value for current item iteration
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];

        for (int i = 0; i < weights.length; i++) {
            // Traverse capacity backwards to avoid reusing the same item multiple times
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values  = {3, 4, 5, 6};
        int capacity = 5;
        System.out.println("Max value in knapsack: " + knapsack(weights, values, capacity));
        // Output: 7 (item 0 and 1: weight 2+3=5, value 3+4=7)
    }
}

// Pseudocode — decision logic for choosing approach
public class DPApproachSelector {
    public static String chooseApproach(
        boolean sparseStateSpace,
        boolean largeInput,
        boolean spaceCritical,
        boolean codeClarityPreferred
    ) {
        if (sparseStateSpace) {
            // Many subproblems will never be reached
            return "Memoization";
        }
        
        if (largeInput && (spaceCritical || recursionDepthConcern)) {
            // Use tabulation with space optimization
            return "Tabulation (space-optimized)";
        }
        
        // Default: tabulation is safer for production
        // Memoization only if clarity is paramount and input small
        if (codeClarityPreferred && !largeInput) {
            return "Memoization (for readability)";
        }
        return "Tabulation";
    }
}