Tabulation is a fundamental concept in Dynamic programming (DP), which entails dividing a problem into smaller subproblems and an array to hold the outcomes of these subproblems.
What is Tabulation?
One of the two primary methodologies in dynamic programming is tabulation, and memoization serves as the other. Tabulation creates a table (often an array) and fills it up one row at a time. It begins with resolving the smallest subproblems first and builds up towards larger subproblems using those answers until the main problem is resolved.
- A bottom-up strategy in dynamic programming is tabulation.
- The outcomes of the subproblems are kept in a table, which is often an array.
- Comparing tabulation to memoization in terms of time complexity, tabulation is often more effective.
Steps to Implement Tabulation:
Tabulation follows these steps:
- Determine the factors that need to be optimized and clearly identify the issue you’re trying to solve.
- Make a table to hold the outcomes of the subproblems (often an array). The problem determines the table’s size.
- Create base cases or initial values for the Table. These numbers stand in for the answers to the smallest subproblems.
- Fill in the table from the smallest subproblems to the largest using iteration (usually loops). Based on previously calculated subproblems, determine the solutions to each subproblem.
- Once the table is fully filled, the final result is usually found in the last entry of the table.
Let’s take an example: Fibonacci Sequence
Follow the steps to solve the problem using Dynamic Programming(tabulation):
- Find the nth Fibonacci number.
- Create an array fib to store intermediate Fibonacci numbers.
- Initialize the Table: fib[0] = 0 fib[1] = 1
- Use a loop to calculate fib[i] = fib[i-1] + fib[i-2] for i from 2 to n.
- The nth Fibonacci number is fib[n].
Below is the implementation of the above idea:
C++
#include <iostream>#include <vector>int fibonacci_tabulation(int n) { // Create a vector to store Fibonacci numbers std::vector<int> fib(n + 1, 0); // Base cases // Smallest subproblems fib[0] = 0; fib[1] = 1; // Fill in the vector using tabulation // Filling the rest of the vector from // smaller subproblems for (int i = 2; i <= n; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } // Return the nth Fibonacci number return fib[n];}int main() { int n = 10; int result = fibonacci_tabulation(n); std::cout << result << std::endl; return 0;} |
Python
def fibonacci_tabulation(n): # Create an array to store Fibonacci numbers fib = [0] * (n + 1) # Base cases # Smallest subproblems fib[0] = 0 fib[1] = 1 # Fill in the table using tabulation # Filling the rest of the table from # smaller subproblems for i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2] # Return the nth Fibonacci number return fib[n]# Driver Coden = 10result = fibonacci_tabulation(n)print(result) |
55
Conclusion:
Tabulation is a powerful technique in dynamic programming for solving complex problems efficiently by storing subproblems results in array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
