使用动态规划求最长回文子序列

1. Overview

In this tutorial, we’ll explain the longest palindromic subsequence problem.

First, we’ll describe the problem with some basic definitions. Next, we’ll show some example sequences and their respective longest palindromic subsequences.

Finally, we’ll explain the top-down and the bottom-up dynamic programming approaches.

To learn more about the basics of dynamic programming before diving into the problem at hand, we’d suggest checking out some other tutorials as well. The knapsack or Longest Increasing Subsequence are basic dynamic programming problems and are easy ones to start with.

2. Definitions

First, let’s understand the problem correctly and give some definitions.

1. Subsequence: A subsequence taken from an array of elements is a sequence that is obtained by deleting some (possibly zero) elements from the original sequence. In other words, it’s a sequence taken from the original sequence without changing the relative order of the taken elements. For example, bdf is a subsequence of abcdefg. Also, we consider xyz to be a subsequence of the same xyz sequence. However, abd is not a subsequence of baed because we changed the order of a and b in the original sequence.
2. Palindrome: A palindrome is any sequence that we can read the same forward and backward. For example, abcba and byzzyb are palindrome sequences, while abca is not.

Therefore, the discussed problem can be defined simply: given a sequence of elements, our task is to find the length of the longest subsequence that is a palindrome.

3. Examples

Take a look at the table that shows examples of different sequences along with their respective longest palindromic subsequences.

In this problem, we’re only interested in the length of the longest palindromic subsequence. Thus, it doesn’t matter how many palindromic subsequences we find.

4. Dynamic Programming Approach

In order to build a dynamic programming solution, we must separate the problem into smaller subproblems. We call each subproblem a state. By combining the answers of subproblems, we can reach the answer to the full problem.

Let’s think about the subproblems of our current problem. The full problem requires finding the answer to the full sequence. For a subproblem, we’ll find the answer to a specific range from the original sequence.

There are three reasons for choosing this type of subproblem.

The first reason is that the base subproblem is one of two options. When we need to calculate the answer to a range of length 1, its answer equals to one. That’s because any sequence of length one is a palindrome. Otherwise, if we reach an empty range, the answer to it is just zero.

The second reason is that the palindromic sequence has the first and last elements equal. If we removed these elements, the remaining elements must form a palindromic sequence as well. Therefore, from the state we can move to state if the first and the nth elements are equal.

The last reason is the case of the first and last elements being not equal. In this case, we have two options. We can find the best answer by removing either the first element or the last one. For example, from the state , if the first and nth elements are not equal, we can find the best answer in one of the ranges or .

In order to implement an algorithm for the described approach, we have two types of dynamic programming: the top-down and the bottom-up approaches. Let’s look at each of them in detail.

4.1. Top-Down Approach

The top-down approach is usually easier to understand. In each step, we recursively apply the algorithm to all the subproblems. After that, we calculate the answer to the current problem based on the answers of the subproblems.

Before dividing the problem into subproblems, we check to see if the current state has been calculated before. If so, we just return the calculated answer. Otherwise, we do the recursive calls.

Take a look at the pseudocode of the described approach. In the initial call, we must fill the array with -1 values, indicating that we haven’t calculated any state yet. We must also pass the sequence, equal to one, and equal to , where is the length of the sequence.

algorithm SolveTopDown(dp, sequence, L, R):
    // INPUT
    //   dp = 2D array that stores the answer to states
    //   sequence = The sequence to calculate the answer for
    //   L = The left index of the current range
    //   R = The right index of the current range
    // OUTPUT
    //   The longest palindromic subsequence

    if L > R:
        return 0
    else if L = R:
        return 1
    else if dp[L][R] != -1:
        return dp[L][R]
    else if sequence[L] = sequence[R]:
        dp[L][R] <- 2 + Solve(dp, sequence, L + 1, R - 1)
    else:
        moveL <- Solve(dp, sequence, L + 1, R)
        moveR <- Solve(dp, sequence, L, R - 1)
        dp[L][R] <- max(moveL, moveR)

    return dp[L][R]

As we can see, If we’ve reached a base subproblem, we return its answer. Also, if we’ve calculated this state before, we return its answer.

Otherwise, if both sides of the range hold equal elements, we calculate the best answer we can get from the subproblem . After that, we add 2 to the current state’s answer because we included the Lth and Rth elements in the palindromic subsequence.

If the Lth and Rth elements are not equal, we have two options. We can either move one step forward or move one step backward. The final answer is the maximum value between the two options. It’s worth noting that we store the answer inside the array so that we can reuse it if we reach the same state later.

The time complexity of the above approach is , where is the length of the sequence. The reason is that we calculate each state exactly once. Therefore, once the array is filled, we immediately return the answer without doing any more calculations.

4.2. Bottom-Up Approach

In the bottom-up approach, we calculate the answer to small subproblems and then move to the bigger subproblems.

For simplicity, we’ll change the state a little. We’ll consider the state to store the answer of the range that starts from and has a length of . Let’s have a look at the pseudocode:

algorithm SolveBottomUp(sequence, n):
    // INPUT
    //   sequence = The sequence to calculate the answer for
    //   n = The length of the sequence
    // OUTPUT
    //   Returns the length of the longest palindromic subsequence

    for i <- 1, 2, ..., n:
        dp[i][0] <- 0
        dp[i][1] <- 1

    for len <- 2, 3, ..., n:
        for L <- 1, 2, ..., n - len + 1:
            R <- L + len - 1
            if sequence[L] = sequence[R]:
                dp[L][len] <- 2 + dp[L + 1][len - 2]
            else:
                moveL <- dp[L + 1][len - 1]
                moveR <- dp[L][len - 1]
                dp[L][len] <- max(moveL, moveR)

    return dp[1][n]

First, we store the answer to the two base subproblems. Next, we iterate over all possible lengths. Note that we iterate over lengths in increasing order because we need to start from smaller subproblems and reach the bigger ones.

If both ends of the range match, we move to the next element after increasing the length by two. Otherwise, if both ends don’t match, we check the answer of the smaller range that starts either from or from . After that, we store the maximum between both of these options. Finally, the answer to the full problem is stored inside .

The complexity of the bottom-up approach is also , where is the length of the sequence, similar to the top-down complexity.

5. Conclusion

In this tutorial, we explained the longest palindromic subsequence problem. Also, we gave some examples of that problem. Finally, we showed the top-down and bottom-up dynamic programming approaches to solve the problem, along with the complexity of each approach.