Memoization vs Tabulation in Dynamic Programming
Difference between Memoization and Tabulation in DP
Before diving into Memoization vs Tabulation in Dynamic Programming first we have to get clear about Dynamic Programming (DP) which is a crucial technique in computer science and programming used to solve problems by breaking them down into overlapping subproblems. Two primary methods in dynamic programming are Memoization and Tabulation, each with distinct advantages and applications.
In this article, we will explore both approaches in depth, provide Java implementations, discuss when to use each, and analyze the space and time complexity.
What is Dynamic Programming?
What is Dynamic Programming?
Dynamic Programming is used when a problem can be divided into subproblems that are solved only once and their results are reused multiple times.
Such problems exists like:
- Overlapping Subproblems: The same subproblems are solved multiple times.
- Optimal Substructure: The optimal solution can be constructed from the optimal solutions of subproblems.
Common problems solvable by DP include:
- Fibonacci Sequence
- Longest Common Subsequence
- 0/1 Knapsack Problem
- Coin Change
- Matrix Chain Multiplication
Memoization vs Tabulation in Dynamic Programming
What is Memoization? (Top Down Approach)
- Memoization involves solving the problem recursively while storing the results of subproblems in a cache to avoid redundant computations.
- It’s called a top down approach because we start solving from the main problem and move towards smaller subproblems.
Characteristics:
- Uses recursion
- Employs caching to avoid recomputation
- Typically uses arrays or hash maps for storing results
- Suitable for problems with sparse subproblem space
Example Code: Fibonacci Series using Memoization
import java.util.Arrays;
public class FibonacciMemoization {
static int[] dp;
static int fib(int n) {
if (n <= 1)
return n;
if (dp[n] != -1)
return dp[n];
dp[n] = fib(n - 1) + fib(n - 2);
return dp[n];
}
public static void main(String[] args) {
int n = 10;
dp = new int[n + 1];
Arrays.fill(dp, -1);
System.out.println("Fibonacci of " + n + " is " + fib(n));
}
}
Output:
Fibonacci of 10 is 55
Space Complexity: O(n) due to memoization array and recursion stack
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
What is Tabulation? (Bottom Up Approach)
- Tabulation solves the problem iteratively from the smallest subproblems and uses their results to build up to the solution of the original problem.
- It’s a bottom up technique that avoids recursion entirely.
Characteristics:
Uses iteration
Constructs a table to store solutions
More efficient in terms of recursion stack space
Solves all subproblems, even unnecessary ones
Example Code: Fibonacci Series using Tabulation
public class FibonacciTabulation {
static int fib(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) {
int n = 10;
System.out.println("Fibonacci of " + n + " is " + fib(n));
}
}
Fibonacci of 10 is 55
Space Complexity: O(n) due to the dp array
Space Optimized Version of Solution for Fibonacci Series
public class FibonacciOptimized {
static int fib(int n) {
if (n <= 1)
return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci of " + n + " is " + fib(n));
}
}
Output:
Fibonacci of 10 is 55
Space Complexity: O(1)
Memoization vs Tabulation in Dynamic Programming
Example of Solving Knapsack Problem
Problem Statement:
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value.
Memoization Approach (Top-Down)
import java.util.Arrays;
public class KnapsackMemoization {
static int[][] dp;
static int knapsack(int[] wt, int[] val, int W, int n) {
if (n == 0 || W == 0)
return 0;
if (dp[n][W] != -1)
return dp[n][W];
if (wt[n - 1] <= W)
dp[n][W] = Math.max(val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1),
knapsack(wt, val, W, n - 1));
else
dp[n][W] = knapsack(wt, val, W, n - 1);
return dp[n][W];
}
public static void main(String[] args) {
int[] wt = {1, 3, 4, 5};
int[] val = {10, 40, 50, 70};
int W = 8;
int n = wt.length;
dp = new int[n + 1][W + 1];
for (int[] row : dp)
Arrays.fill(row, -1);
System.out.println("Maximum value = " + knapsack(wt, val, W, n));
}
}
Output:
Maximum value = 110
Tabulation Approach (Bottom Up)
public class KnapsackTabulation {
static int knapsack(int[] wt, int[] val, int W, int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
public static void main(String[] args) {
int[] wt = {1, 3, 4, 5};
int[] val = {10, 40, 50, 70};
int W = 8;
int n = wt.length;
System.out.println("Maximum value = " + knapsack(wt, val, W, n));
}
}
Output:
Maximum value = 110
Space Complexity: O(n * W)
Memoization vs Tabulation in Dynamic Programming
| Feature | Memoization | Tabulation |
|---|---|---|
| Approach | Top-down | Bottom-up |
| Uses Recursion | Yes | No |
| Space for Stack | Yes | No |
| Caching | Selective | Complete Table |
| Efficiency | Good for sparse problems | Better for dense problems |
| Easy to Implement | Easier from recursion | Requires loop construction |
Major Difference between Memoization and Tabulation
What to use, when ?
Use Memoization:
- When a natural recursive structure exists
- When some subproblems may not need solving
- If recursion stack space is not a concern
Use Tabulation:
- To avoid recursion overhead
- When all subproblems are necessary
- To implement space optimization
To wrap it up….
Memoization and Tabulation are foundational concepts in dynamic programming, each suited for different types of problems.
Memoization is intuitive and easier to apply when converting a recursive algorithm, while Tabulation offers more control and optimization in terms of performance. Both are essential tools that every programmer should master for tackling complex algorithmic challenges effectively.
FAQ's related to Memoization vs Tabulation
Answer:
Tabulation is a dynamic programming technique where we solve the problem by working from the bottom up.
We first solve the smaller parts of the problem and store their results in an array or table.
Then we use those stored results to solve the bigger parts. It does not use recursion: instead, we use loops to build the answer step by step.
Answer:
Memoization is another dynamic programming method that works in a top down way. We use recursion to solve the main problem, and if we come across a smaller subproblem, we solve it only once and store its result.
When the same subproblem is needed again, we just return the saved answer instead of solving it again. This helps save time by avoiding repeated work.
Answer:
The main difference is in how they approach the problem.
- Memoization starts from the main problem and breaks it down into smaller subproblems using recursion.
- Tabulation starts by solving the smallest subproblems first and builds up the solution using loops.
- Memoization uses extra memory for the recursion stack, while tabulation does not.
Tabulation is usually faster because it avoids the overhead of function calls.
Answer:
Biggest advantage of tabulation is that it doesn’t use recursion, so there’s no risk of stack overflow, even for large inputs.
It also tends to be faster because it avoids the extra cost of function calls and recursion.
Answer:
Memoization has a few drawbacks:
- It uses recursion, which can lead to stack overflow if the input size is too large.
- It may use more memory if many subproblems are stored.
- Recursive code can sometimes be harder to understand and debug.
- It might be slightly slower due to repeated function calls.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
