Memoization vs Tabulation — The 10000-Stack-Frame Gotcha

Dynamic programming is one of those topics that separates candidates who 'know algorithms' from those who truly understand them. Every LeetCode grind session eventually runs into it — Fibonacci, coin change, longest common subsequence, knapsack. But here's what most tutorials skip: DP isn't just about finding the recurrence relation. It's about HOW you execute it, and that choice — memoization or tabulation — has real consequences for your code's readability, performance, and risk of a StackOverflowError in production.

Both approaches solve the same core problem: overlapping subproblems. Without DP, a naive recursive solution recomputes the same results exponentially. With DP, you store those results. The question is whether you store them lazily (top-down memoization) or eagerly (bottom-up tabulation). That distinction isn't just academic — it changes your call stack usage, your space complexity in practice, and how easy your code is to debug.

By the end of this article you'll be able to implement the same problem both ways, explain the trade-offs out loud to an interviewer without hesitation, and make a confident choice between the two approaches based on the problem in front of you. Let's build this understanding from the ground up.

Memoization vs Tabulation — The 10000-Stack-Frame Gotcha

Memoization and tabulation are the two core strategies for dynamic programming. Memoization is a top-down approach: you cache the results of recursive calls so you never recompute the same subproblem twice. Tabulation is bottom-up: you fill a table iteratively, starting from the smallest subproblems and building up to the target. Both eliminate redundant computation, but they differ fundamentally in control flow and memory footprint.

Memoization keeps the recursive structure of the original problem, which often makes it easier to write and reason about. But it pays a hidden cost: each recursive call adds a stack frame. For problems with depth proportional to input size — like Fibonacci with n=10000 — you'll blow the call stack before you ever hit a cache hit. Tabulation avoids recursion entirely, using loops and a flat array, so stack depth is O(1). It also gives you precise control over memory layout, which matters when the table is large.

Use memoization when the recursion depth is bounded (e.g., tree DP with log-depth) or when you only need a subset of subproblems. Use tabulation when the full subproblem space is needed or when stack depth is a concern — which is most real-world DP. The choice isn't about speed; it's about whether your program crashes or completes.

Top-Down Memoization: Solving Only What You Need

Memoization starts from the question you want answered and works backwards. You write a recursive function that breaks the problem into smaller subproblems — exactly like you would with plain recursion — but before computing anything, you check a cache. If the answer is already there, you return it instantly. If not, you compute it, store it, and return it.

This approach is called 'top-down' because you start at the top (the full problem) and drill down only as far as you need. If your problem has 100 possible subproblems but the answer only requires 40 of them, you only ever compute those 40. That's memoization's killer feature: it's lazy. It doesn't do work it doesn't have to.

The trade-off is the call stack. Every recursive call adds a frame. On deep problems — think Fibonacci(10000) — you'll hit Java's default stack limit and get a StackOverflowError. Memoization also carries the overhead of HashMap lookups if your subproblem keys aren't simple integers.

Use memoization when your problem has a natural recursive structure, when not all subproblems need to be solved, or when you're prototyping quickly and want code that reads close to the mathematical definition of the recurrence.

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);
    }
}

Bottom-Up Tabulation: Fill the Table, Then Read the Answer

Tabulation flips the script entirely. Instead of starting at the answer and recursing down, you start at the smallest possible subproblems and build upward, filling a table (usually an array) until you reach the answer you need.

There's no recursion. No call stack. No risk of StackOverflowError. You loop, you fill, you read the final cell. That's it. This is called 'bottom-up' because you lay a foundation of small solutions and stack larger solutions on top of them.

The discipline tabulation requires is figuring out the correct fill order — which cells depend on which. For Fibonacci, fib(n) depends on fib(n-1) and fib(n-2), so you fill left to right. For 2D problems like Longest Common Subsequence, you fill row by row. Getting the order wrong is the primary source of bugs in tabulation code.

Tabulation's other superpower is space optimization. Once you've moved past a row or a few cells, you often don't need them anymore — you can shrink a 2D DP table down to a single array, or shrink a 1D array down to two variables. This kind of optimization is almost impossible with memoization.

Use tabulation when you know every subproblem must be solved anyway, when you're dealing with large inputs where recursion depth is a concern, or when you need maximum performance and predictable memory usage.

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);
    }
}

A Real DP Problem — Coin Change Side by Side

Fibonacci is a teaching toy. Let's use Coin Change — a genuinely hard problem that appears constantly in interviews — to see how the two approaches feel different in practice.

The problem: given a list of coin denominations and a target amount, what's the minimum number of coins needed to make that amount? There's no greedy solution that always works here. You need DP.

The recurrence is: minCoins(amount) = 1 + min(minCoins(amount - coin)) for every coin that fits. Both approaches encode this same logic. What changes is the execution model.

With memoization you'll write something that looks almost identical to the mathematical definition of the recurrence. With tabulation you'll think about it differently — 'what's the minimum coins for every amount from 0 up to target?' and build that answer cell by cell.

Studying the same problem through both lenses is the fastest way to internalize when each approach feels natural. Memoization felt easier to write here — the recursive logic maps directly to the problem statement. But tabulation is more efficient and avoids any stack depth concerns for large amounts.

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));
    }
}

Space-Time Trade-offs: When Tabulation Wins on Memory

A common misconception is that memoization always uses less memory because it only caches visited states. But in practice, the opposite is often true — tabulation can be aggressively optimized to use far less space.

Consider the classic 0/1 Knapsack problem. Memoization stores results for every (item, remaining capacity) pair that is reached. If the recursion explores many state combinations, the cache can grow to O(NW). Tabulation uses the same O(NW) table, but you can compress it: since dp[i][c] only depends on dp[i-1][c] and dp[i-1][c-w], you can discard rows before i-1. This compresses to O(W) space — just one array.

Memoization can't easily drop old states because the recursion may jump back to any previous state. You'd need a full-access cache. The theoretical space complexity is the same, but tabulation's iterative nature lets you be ruthless with discarding.

This isn't a theoretical edge — it's why production-grade DP almost always uses tabulation with space compression. When your problem involves 10^5 items and capacity 10^5, O(N*W) is 10^10 — impossible. O(W) with 10^5 is 400KB. That's the difference between a deployable solution and a crash.

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)
    }
}

Choosing the Right Approach: Decision Tree

You don't need to agonize over memoization vs tabulation every time. A simple decision tree gets you to the right answer fast.

First, ask: 'Do I need to solve every subproblem?' If your problem has a sparse state space where many states are unreachable from the target (e.g., some graph DP problems), memoization will skip those states and save time. Tabulation would waste cycles filling unreachable cells.

Second, ask: 'Is recursion depth a concern?' If the maximum recursion depth could exceed 5000 (and you can't increase stack size in your environment), pick tabulation. Serverless environments often have tight stack limits.

Third, ask: 'Can I optimize space with tabulation?' If you can reduce a 2D table to 1D, that's almost always worth it. The iterative fill order is the key enabler.

Finally, ask: 'How important is code readability for this specific codebase?' If you're writing a one-off analysis script that won't be maintained, memoization's clarity wins. If this is a core library function that will be called millions of times, use tabulation with compression.

// 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";
    }
}

The Rod Cutting Problem: Where Tabulation Buries Recursion

Competitors love the rod cutting problem to show DP in action, but they tip-toe around the real truth: for this problem, tabulation is the only sane choice when n hits anything above a few hundred. The recursive memoized version doesn't just hit stack limits—it butchers your cache locality. Every recursive call sprays your call stack across memory pages. Tabulation? A single contiguous array, linear access pattern, CPU prefetch running at full speed.

Here's the concrete difference: rod cutting with memoization requires O(n^2) time and O(n) space, but that 'space' lives on the call stack. Real production stacks are maybe 8 MB default on a JVM. For n=1000, your recursive depth is n, each frame holds state. That's not just slow—it's a guaranteed StackOverflowError waiting for a spike in input size.

Bottom-up tabulation solves it iteratively: for each length from 1 to n, you scan every possible cut, track the best value in a one-dimensional array. No function calls, no stack frames, just a double loop and an array index. The algorithm is literally: table[i] = max(price[j] + table[i - j - 1]) for all j < i. You don't 'think' in recursion—you think in loops. That's why production DP almost always defaults to tabulation when the entire subproblem space is needed.

// io.thecodeforge — dsa tutorial

public class RodCuttingTabulation {

    public static int maxRevenue(int[] prices, int rodLength) {
        int[] dp = new int[rodLength + 1];
        for (int len = 1; len <= rodLength; len++) {
            int best = 0;
            for (int cut = 0; cut < len; cut++) {
                int revenue = prices[cut] + dp[len - cut - 1];
                if (revenue > best) best = revenue;
            }
            dp[len] = best;
        }
        return dp[rodLength];
    }

    public static void main(String[] args) {
        int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
        System.out.println("Max revenue for length 8: " + maxRevenue(prices, 8));
    }
}

Subproblem Space: Why Laziness Isn't Always a Virtue

Memoization's killer feature is laziness—it only computes what the recursion actually touches. That sounds smart until you realize that many DP problems, like the classic 'minimum path sum' in a grid, still require exploring the entire space. You're paying the cost of function call overhead and a hash map lookup for every cell, even when you'd be forced to compute them all anyway.

Tabulation doesn't distinguish between 'needed' and 'not needed' because it fills the entire table. That's a disadvantage when the subproblem graph is sparse—like in certain tree DP where only a fraction of states are reachable. But for the common case (grids, sequences, knapsacks), the subproblem space is a full rectangle. Every cell matters. Tabulation's constant factor is lower: no hash map collisions, no recursion frame setup, no GC pressure from throwing away memo entries.

Here's the bottom line: if your state space is O(n*m) and every state is reachable, tabulation wins by a factor of 2-5x. If the problem has narrow dependency paths (e.g., optimal BST), memoization can skip entire branches. Profile before you preach. But for 90% of DP problems on LeetCode or in production, tabulation is the default.

// io.thecodeforge — dsa tutorial

public class MinPathSumTabulation {

    public static int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        for (int c = 1; c < cols; c++) dp[0][c] = dp[0][c-1] + grid[0][c];
        for (int r = 1; r < rows; r++) dp[r][0] = dp[r-1][0] + grid[r][0];
        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                dp[r][c] = grid[r][c] + Math.min(dp[r-1][c], dp[r][c-1]);
            }
        }
        return dp[rows-1][cols-1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println("Min path sum: " + minPathSum(grid));
    }
}

House Robber: Why Memoization Fails on Linear State

Memoization feels clean until you hit a problem where subproblem order doesn't matter. House Robber is that problem. You're robbing houses on a street, can't touch adjacent ones, maximize your haul. The recurrence is trivial: rob(n) = max(rob(n-1), rob(n-2) + nums[n]).

Memoization works here, but it's overkill. You're climbing the recursion tree for every house, burning stack frames and overhead for a problem that has a single, linear dependency chain. The stack depth equals the number of houses — 10,000 houses means 10,000 frames. In production, that's a stack overflow waiting to happen when someone passes a city block.

The real issue: memoization hides the fact that you only ever need the last two subproblems. You're caching an entire array of results you'll never reuse. It's a waste of memory and a ticking bomb for recursion limits. Senior engineers don't solve linear DP with recursion — they use tabulation and move on.

// io.thecodeforge — dsa tutorial

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

public class HouseRobberMemo {
    private static int rob(int[] nums, int i, Map<Integer, Integer> cache) {
        if (i < 0) return 0;
        if (cache.containsKey(i)) return cache.get(i);
        int result = Math.max(rob(nums, i-1, cache), rob(nums, i-2, cache) + nums[i]);
        cache.put(i, result);
        return result;
    }

    public static void main(String[] args) {
        int[] houses = {2, 7, 9, 3, 1};
        System.out.println(rob(houses, houses.length-1, new HashMap<>()));
    }
}

House Robber: Tabulation Beats Recursion Flat

Tabulation for House Robber is a one-liner disguise: two variables, no recursion, no cache, no stack. You iterate forward, keeping track of the max money you could've taken up to the last two houses. That's it. No function calls, no hash map lookups, no stack frames. Just a loop and a swap.

The WHY: The recurrence only depends on the immediate previous two results. You don't need to store anything else. This is the pattern for any linear DP — Fibonacci, climbing stairs, house robber. They're all the same under the hood. Senior engineers spot this immediately and write the O(1) space solution rather than the O(n) memoization silliness.

In production, this matters. You're not just saving memory — you're eliminating the unpredictability of recursion overhead. A loop is deterministic. The JIT compiles it to a tight jump instruction. The recursive version generates stack frames and garbage for the GC. For a system handling thousands of calls per second, the tabulation version is the only real option.

// io.thecodeforge — dsa tutorial

public class HouseRobberTab {
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int prev2 = 0, prev1 = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    public static void main(String[] args) {
        int[] houses = {2, 7, 9, 3, 1};
        System.out.println(rob(houses));
    }
}

Example-Driven Understanding: When Memoization Hits the Wall

Theory is cheap. The real test is running code. Consider the Fibonacci sequence: simple, pure, and a perfect trap. Memoization solves it with O(n) time and recursion depth up to n. For n=10,000, most JVMs blow the stack — not because the algorithm is wrong, but because recursion eats frames. Tabulation, on the other hand, uses a loop and an array. No stack frames beyond one. The bottom-up approach runs n=10^6 without blinking. The why: recursion inherently ties your computation to call-stack depth. Even with memoization, the call tree collapses to O(n) calls, but each call still occupies a frame. Tabulation eliminates that overhead entirely. If your subproblem space is large and sequential, tabulation isn't just faster — it's viable where memoization crashes.

// io.thecodeforge — dsa tutorial

public class MemoVsTabFib {
    // Memoization — elegant, but stack-bound
    static int fibMemo(int n, int[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    }

    // Tabulation — no recursion, unlimited depth
    static int fibTab(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibMemo(40, new int[41])); // 102334155
        System.out.println(fibTab(40));              // 102334155
        // fibMemo(10000) throws StackOverflowError
    }
}

Conclusion: The One Rule That Ends the Debate

After all the comparisons, one principle settles the choice: structure of the subproblem dependency graph. If dependencies form a tree or contain overlapping recursive branches with moderate depth, memoization wins — you compute only what you need. If dependencies form a grid, sequence, or any regular lattice where each cell depends on prior cells in a fixed order, tabulation dominates. The why is mechanical: tabulation avoids recursion overhead, stack limits, and cache misses from deep call chains. Memoization is lazy and elegant; tabulation is brute force and reliable. In production systems processing thousands of inputs, tabulation’s deterministic control flow and constant stack depth make it the default. Memoization belongs in prototypes, interview whiteboards, and problems where the subproblem space is sparse. For everything else, fill the table bottom-up and read the answer. No ambiguity, no stack traces at 2 AM.

// io.thecodeforge — dsa tutorial

public class ConclusionCheck {
    // Dependency graph check: linear? -> tabulation. Sparse tree? -> memoization.
    static boolean isLinearDependency(int n) {
        // If subproblem i depends only on i-1, i-2 -> linear
        return true; // placeholder for your real check
    }

    public static void main(String[] args) {
        String choice = isLinearDependency(100) ? "tabulation" : "memoization";
        System.out.println("For linear chains, use: " + choice);
    }
}