Problem Statement
What is the difference between memoization and tabulation in dynamic programming?
Explanation
Memoization is a top-down approach that uses recursion with caching. It starts with the original problem and recursively breaks it down, storing results in a cache. Tabulation is a bottom-up approach that uses iteration, starting from the smallest subproblems and building up to the solution.
Memoization computes only the required subproblems on-demand, while tabulation computes all subproblems. Memoization has recursion overhead but may skip unnecessary computations. Tabulation avoids recursion overhead and has better space optimization potential. Both have the same time complexity but different implementation styles.
Code Solution
SolutionRead Only
// Memoization - Top-down with recursion
int dpMemo(int n, Map<Integer, Integer> memo) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = dpMemo(n-1, memo) + dpMemo(n-2, memo);
memo.put(n, result);
return result;
}
// Solves from F(n) down to F(0)
// Tabulation - Bottom-up with iteration
int dpTab(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];
}
// Solves from F(0) up to F(n)
// Memoization: Recursive, cache as needed
// Tabulation: Iterative, fill entire tablePractice Sets
This question appears in the following practice sets:
