WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Tabulation Technique: Introduction
Understanding Tabulation
Tabulation is a dynamic programming technique that solves problems by filling up a table iteratively. Unlike memoization, which works top-down, tabulation follows a bottom-up approach.
Example 1: Fibonacci Numbers
Problem Statement
Calculate the nth Fibonacci number using tabulation.
int fibonacci(int n) {
if (n <= 1) return n;
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
Console Output:
Fibonacci of 5 is 5
Example 2: Knapsack Problem
Problem Statement
Solve the 0/1 knapsack problem using tabulation.
int knapsack(int[] weights, int[] values, int W) {
int n = weights.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
Console Output:
Maximum value in Knapsack = 220
Example 3: Longest Common Subsequence (LCS)
Problem Statement
Find the length of the longest common subsequence between two strings using tabulation.
int lcs(String X, String Y) {
int m = X.length(), n = Y.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
Console Output:
Length of LCS is 4
Example 4: Minimum Edit Distance
Problem Statement
Calculate the minimum edit distance between two strings using tabulation.
int minEditDistance(String str1, String str2) {
int m = str1.length(), n = str2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
}
}
}
return dp[m][n];
}
Console Output:
Minimum Edit Distance is 3
Example 5: Coin Change Problem
Problem Statement
Determine the fewest number of coins needed to make up a given amount using tabulation.
int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
Console Output:
Fewest coins needed: 3
