Dynamic Programming – Tabulation

Tabulation is preferred over memoization is when solving a problem with a large number of possible states. In such cases, memoization may lead to stack overflow errors or consume too much memory due to the recursion depth, while tabulation can handle a large number of states efficiently.

One such problem is the Longest Common Subsequence (LCS) problem. Given two sequences of characters, the task is to find the length of the longest subsequence that is common to both sequences. Here, a subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, for the sequences “ABCDGH” and “AEDFHR”, the LCS is “ADH” with a length of 3.

Let’s consider the recursive approach for solving this problem using memoization:

def lcs_memo(X, Y, m, n, memo):
    if m == 0 or n == 0:
        return 0
    if memo[m][n] != -1:
        return memo[m][n]
    if X[m-1] == Y[n-1]:
        memo[m][n] = 1 + lcs_memo(X, Y, m-1, n-1, memo)
    else:
        memo[m][n] = max(lcs_memo(X, Y, m, n-1, memo), lcs_memo(X, Y, m-1, n, memo))
    return memo[m][n]

X = "ABCDGH"
Y = "AEDFHR"
m = len(X)
n = len(Y)
memo = [[-1 for j in range(n+1)] for i in range(m+1)]
print(lcs_memo(X, Y, m, n, memo))

Here, we are using memoization to store the length of the LCS for a given pair of sequences and their lengths in a two-dimensional memo array. The time complexity of this approach is O(mn), where m and n are the lengths of the input sequences.

Now, let’s consider the tabulation approach for solving the same problem:

def lcs_tabu(X, Y):
    m = len(X)
    n = len(Y)
    tabu = [[0 for j in range(n+1)] for i in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                tabu[i][j] = 1 + tabu[i-1][j-1]
            else:
                tabu[i][j] = max(tabu[i][j-1], tabu[i-1][j])
    return tabu[m][n]

X = "ABCDGH"
Y = "AEDFHR"
print(lcs_tabu(X, Y))

Here, we are using a two-dimensional tabu array to store the length of the LCS for all possible pairs of prefixes of the input sequences. The time complexity of this approach is also O(mn).

In this case, tabulation is preferred over memoization because the recursive approach with memoization can consume too much memory due to the recursion depth, while tabulation can handle a large number of states efficiently. Additionally, tabulation has the advantage of being more readable and easier to understand for many programmers.