Tabulation Pattern
What is Tabulation?
Tabulation is a bottom-up dynamic programming technique where we build a table iteratively, starting from the base cases and working our way up to the original problem.
Unlike memoization, which is top-down and uses recursion, tabulation is iterative and builds the solution from the ground up.
When to Use Tabulation
Tabulation is useful when:
- You need to compute all subproblems
- You want to avoid recursion stack overflow
- The problem has a clear iterative structure
- You need to optimize space complexity
Tabulation Template
- Define the state and create a table (array/matrix) to store results
- Initialize the base cases in the table
- Iterate through the table in a bottom-up manner
- Fill each cell using the recurrence relation
- Return the final result from the table
Example: Fibonacci
Here's a tabulation solution for computing the nth Fibonacci number:
Example: Knapsack Problem
Here's a tabulation solution for the 0/1 knapsack problem:
Example: Longest Common Subsequence
Here's a tabulation solution for finding the longest common subsequence:
Pros and Cons of Tabulation
Pros:
- Avoids recursion and stack overflow issues
- Often more efficient in terms of constant factors
- Easier to optimize for space complexity
Cons:
- May compute unnecessary subproblems
- Sometimes less intuitive than the recursive approach
- May be harder to implement for complex state transitions
Pattern 2: Tabulation
Learn how to build solutions iteratively using tables to store results of subproblems.
What is Tabulation?
Tabulation is a bottom-up dynamic programming technique where we build a table iteratively, starting from the base cases and working our way up to the original problem.
Unlike memoization, which is top-down and uses recursion, tabulation is iterative and builds the solution from the ground up.
Key Insight: Tabulation eliminates the overhead of recursion and ensures that each subproblem is solved exactly once in a predetermined order, making it more efficient for problems where all states need to be computed.
When to Use Tabulation
Complete Computation
When you need to compute all subproblems, as tabulation systematically fills the entire table.
Avoiding Stack Overflow
When the recursive approach might lead to stack overflow due to the depth of recursion, as tabulation is iterative.
Space Optimization
When you need to optimize space complexity, as tabulation often allows for more straightforward space optimizations.
The Tabulation Template
1Define State
Define what each cell in the table represents and create a table (array/matrix) of appropriate dimensions.
2Initialize Base Cases
Initialize the base cases in the table, which are the simplest subproblems that can be solved directly.
3Determine Order
Determine the order in which to fill the table, ensuring that when computing a cell, all its dependencies have already been computed.
4Fill Table
Iterate through the table in the determined order, filling each cell using the recurrence relation that relates it to previously computed cells.
5Return Result
Return the final result from the table, which is typically the value in the cell that represents the original problem.
Pseudocode Template:
function solve(params):
// Define the dimensions of the table
dp = createTable(dimensions)
// Initialize base cases
initializeBaseCases(dp)
// Fill the table in bottom-up manner
for each state in bottom-up order:
dp[state] = compute using previously filled states
// Return the final result
return dp[finalState]Example: Fibonacci
Here's a tabulation solution for computing the nth Fibonacci number:
1234567891011121314151617181920212223function fibonacci(n) { // Handle base cases if (n <= 1) return n; // Create a table to store results const dp = new Array(n + 1); // Initialize base cases dp[0] = 0; dp[1] = 1; // Fill the table bottom-up for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } // Return the result return dp[n];} // Example usage:console.log(fibonacci(10)); // Output: 55console.log(fibonacci(40)); // Output: 102334155 (would be very slow without DP)How it works: We create a table dp where dp[i] represents the ith Fibonacci number. We initialize the base cases (dp[0] = 0, dp[1] = 1) and then iteratively fill the table using the recurrence relation dp[i] = dp[i-1] + dp[i-2]. This approach has O(n) time complexity and O(n) space complexity.
Example: Knapsack Problem
Here's a tabulation solution for the 0/1 knapsack problem:
123456789101112131415161718192021222324252627282930313233function knapsack(weights, values, capacity) { const n = weights.length; // Create a 2D table to store results // dp[i][w] represents the maximum value that can be obtained // using the first i items with a knapsack capacity of w const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0)); // Fill the table bottom-up for (let i = 1; i <= n; i++) { for (let w = 0; w <= capacity; w++) { // If the current item is too heavy, skip it if (weights[i - 1] > w) { dp[i][w] = dp[i - 1][w]; } else { // Otherwise, take the maximum of including or excluding the item dp[i][w] = Math.max( dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1] ); } } } // Return the maximum value return dp[n][capacity];} // Example usage:const weights = [2, 3, 4, 5];const values = [3, 4, 5, 6];const capacity = 8;console.log(knapsack(weights, values, capacity)); // Output: 10 (items with values 4 and 6)How it works: We create a 2D table dp where dp[i][w] represents the maximum value that can be obtained using the first i items with a knapsack capacity of w. For each item, we have two choices: include it or exclude it. We take the maximum of these two options. This approach has O(n*W) time complexity and O(n*W) space complexity, where n is the number of items and W is the capacity.
Example: Longest Common Subsequence
Here's a tabulation solution for finding the longest common subsequence:
1234567891011121314151617181920212223242526272829function longestCommonSubsequence(text1, text2) { const m = text1.length; const n = text2.length; // Create a 2D table to store results // dp[i][j] represents the length of LCS of text1[0...i-1] and text2[0...j-1] const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0)); // Fill the table bottom-up for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { // If the current characters match if (text1[i - 1] === text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { // If they don't match, take the maximum of two possibilities dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } // Return the length of LCS return dp[m][n];} // Example usage:console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3 (LCS is "ace")console.log(longestCommonSubsequence("abc", "abc")); // Output: 3 (LCS is "abc")console.log(longestCommonSubsequence("abc", "def")); // Output: 0 (no common subsequence)How it works: We create a 2D table dp where dp[i][j] represents the length of the LCS of the first i characters of text1 and the first j characters of text2. If the current characters match, we extend the LCS. Otherwise, we take the maximum of two possibilities (skip a character in either string). This approach has O(m*n) time complexity and O(m*n) space complexity, where m and n are the lengths of the two strings.
Pros and Cons of Tabulation
Pros
- Avoids recursion and stack overflow issues
- Often more efficient in terms of constant factors due to less function call overhead
- Easier to optimize for space complexity, as we can often reduce the dimensions of the table
- More predictable in terms of time and space complexity
- Better for problems where all states need to be computed
Cons
- May compute unnecessary subproblems if only a subset of states is needed
- Sometimes less intuitive than the recursive approach, especially for complex problems
- May be harder to implement for complex state transitions
- Requires careful consideration of the order in which to fill the table
- May require more code to handle edge cases and initialization