Tabulation

In dynamic programming, tabulation is a technique used to solve problems by filling a table iteratively. The table, usually a multi-dimensional array, is filled bottom-up starting from the base cases and gradually building up the solutions to larger subproblems.

When it comes to the Longest Common Subsequence problem, the tabulation technique involves using a dynamic programming table to store the lengths of the common subsequences for different prefixes of the input strings.

Let's take a look at an example of how the tabulation technique can be implemented in C#:

1using System;
2
3class Program
4{
5    static int LongestCommonSubsequenceTabulation(string s1, string s2)
6    {
7        int m = s1.Length;
8        int n = s2.Length;
9
10        int[, ] dp = new int[m + 1, n + 1];
11
12        for (int i = 1; i <= m; i++)
13        {
14            for (int j = 1; j <= n; j++)
15            {
16                if (s1[i - 1] == s2[j - 1])
17                {
18                    dp[i, j] = 1 + dp[i - 1, j - 1];
19                }
20                else
21                {
22                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
23                }
24            }
25        }
26
27        return dp[m, n];
28    }
29
30    static void Main(string[] args)
31    {
32        string s1 = "AGGTAB";
33        string s2 = "GXTXAYB";
34
35        int length = LongestCommonSubsequenceTabulation(s1, s2);
36        Console.WriteLine("Length of the Longest Common Subsequence: " + length);
37    }
38}

In the above example, we create a two-dimensional array dp to store the lengths of the common subsequences. We start filling the table from the base cases (empty strings) and gradually build up the solutions to larger subproblems.

By considering all possible prefixes of the input strings, we fill the table using the following logic:

• If the characters at the current positions in both strings are equal, the length of the common subsequence increases by 1 compared to the length of the subsequence without the current characters. Therefore, we add 1 to the diagonal element.
• If the characters are not equal, we take the maximum length of the common subsequences without the current characters from either the previous row or the previous column.

Once we fill the entire table, the bottom-right element of the table represents the length of the longest common subsequence. In our example, the length of the longest common subsequence is 4.

The tabulation technique is a powerful approach to solve problems using dynamic programming. It provides an efficient bottom-up solution and can be used to optimize recursive algorithms by avoiding repetitive computations.

Note: The above example is written in C#, but the same logic can be implemented in other programming languages as well, with appropriate syntax changes.

xxxxxxxxxx

const longestCommonSubsequenceTabulation = (str1, str2) => {

  const m = str1.length;

  const n = str2.length;

​

  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

​

  for (let i = 1; i <= m; i++) {

    for (let j = 1; j <= n; j++) {

      if (str1[i - 1] === str2[j - 1]) {

        dp[i][j] = 1 + dp[i - 1][j - 1];

      } else {

        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

      }

    }

  }

​

  return dp[m][n];

};

​

const str1 = 'AGGTAB';

const str2 = 'GXTXAYB';

const length = longestCommonSubsequenceTabulation(str1, str2);

console.log(`Length of the Longest Common Subsequence: ${length}`);