Memoization vs Tabulation

Memoization and tabulation solve the same recurrence from different directions. Memoization asks only the states it needs. Tabulation fills states in a safe dependency order.

Top-Down and Bottom-Up

Top-down code often looks closer to the recurrence and can skip unreachable states. Bottom-up code avoids recursion depth and can be faster when every state is needed.

Scenario: Recommendation Planning

A recommendation engine explores bundles under constraints. If only a small portion of state space is reachable after business rules, memoization avoids filling irrelevant states. If every budget and item combination is needed for reporting, tabulation is easier to audit.

Same Pattern in Java, Python, and JavaScript

House robber is a 1D DP that can be tabulated with two rolling values.

class HouseRobber {
    static int rob(int[] nums) {
        int twoBack = 0, oneBack = 0;
        for (int value : nums) {
            int current = Math.max(oneBack, twoBack + value);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Solve house robber with bottom-up rolling state.
• Return the fewest coins needed to make an amount.
• Return whether a string can be segmented into dictionary words.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class HouseRobber {
    static int rob(int[] nums) {
        int twoBack = 0, oneBack = 0;
        for (int value : nums) {
            int current = Math.max(oneBack, twoBack + value);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

import java.util.*;
class CoinChange { static int coinChange(int[] coins,int amount){ int[] dp=new int[amount+1]; Arrays.fill(dp, amount+1); dp[0]=0; for(int a=1;a<=amount;a++) for(int c:coins) if(c<=a) dp[a]=Math.min(dp[a],dp[a-c]+1); return dp[amount]>amount?-1:dp[amount]; } }

import java.util.*;
class WordBreak { static boolean can(String s, Set<String> dict){ Boolean[] memo=new Boolean[s.length()+1]; return dfs(s,0,dict,memo); } static boolean dfs(String s,int i,Set<String> dict,Boolean[] memo){ if(i==s.length()) return true; if(memo[i]!=null) return memo[i]; for(int end=i+1;end<=s.length();end++) if(dict.contains(s.substring(i,end)) && dfs(s,end,dict,memo)) return memo[i]=true; return memo[i]=false; } }

Solved modelWorked Interview Answer

Solve house robber with bottom-up rolling values. The recurrence is best(i) = max(best(i-1), best(i-2) + value). Only the previous two states are needed.

class HouseRobber {
    static int rob(int[] nums) {
        int twoBack = 0, oneBack = 0;
        for (int value : nums) {
            int current = Math.max(oneBack, twoBack + value);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Assuming bottom-up is always faster.
• Ignoring recursion depth.
• Filling table in dependency-breaking order.
• Allocating unreachable states unnecessarily.
• Overwriting values needed later.

Execution guardrailQuick-Start Checklist

• Write recurrence first.
• Choose top-down or bottom-up.
• Check reachable state density.
• Check stack depth.
• Define iteration order.
• Consider space compression.
• Explain trade-off.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice coin change, word break, house robber, and edit distance.
• Compare memoization and tabulation for the same recurrence.
• Study iterative dependency ordering carefully.