【LeetCode】动态规划—516. 最长回文子序列（附完整Python/C++代码）

前言

最长回文子序列 问题是动态规划的重要应用之一。在实际生活中，很多信息都可以通过回文子序列来进行抽象和处理。本题旨在通过动态规划的方法，帮助我们有效地找到字符串中的最长回文子序列。

本文将详细阐述该问题的思路，包括如何定义状态、推导递推关系，并提供 Python 和 C++ 的实现代码，帮助读者更深入地理解动态规划的应用。

题目描述

基本思路

1. 问题定义

给定一个字符串 $s$ ，求出该字符串的最长回文子序列的长度。回文子序列是指在字符串中删除一些字符（可以是零个或多个），使得剩下的字符能够组成一个回文字符串。

2. 理解问题和递推关系

• 回文子序列的特性是从两端向中间对称。若字符串的首尾字符相同，那么这两个字符都可以作为回文子序列的一部分。
• 定义 $dp[i][j]$ 为子串 $s[i\dots j]$ 的最长回文子序列的长度。
• 递推关系：
  • 如果 $s[i]==s[j]$ ，那 $dp[i][j]=dp[i+1][j-1]+2$ 。
  • 如果 $s[i]!=s[j]$, 那 $/dp[i][j]=\backslash \max (dp[i+1][j],dp[i][j-1])$ 。
• 边界条件：当 $i==j$ 时，单个字符的最长回文子序列长度为 1 。

3. 解决方法

3.1 动态规划方法

1. 创建一个二维数组 $dp$ ，其大小为 $n\times n$ ，其中 $n$ 是字符串的长度。
2. 初始化对角线上的元素为 1 ，表示每个单独字符的回文子序列长度为 1 。
3. 使用两个嵌套循环填充 $dp$ 数组，从长度 2 开始，直到 $n$：计算毎一对 (i, j) 的回文子序列长度。
4. 最终结果存储在 $dp[0][n-1]$ 中，即整个字符串的最长回文子序列长度。

3.2 空间优化的动态规划

• 由于 $dp[i][j]$ 只依赖于 $dp[i+1][j]$ 和 $dp[i][j-1]$ ，可以将空间复杂度优化到 $O(n)$ ，只使用一维数组进行计算。

4. 进一步优化

• 空间复杂度优化：利用—维数组相代二维数组，减少内存占用。
• 时间复杂度：动态规划的时间复杂度为 $O\left(n^{\wedge }2\right)$ ，可以处理长度适中的字符串。

5. 小总结

• 动态规划提供了一种有效的方法来解决最长回文子序列的问题，能够通过状态转移找到全局最优解。
• 通过对 $dp$ 数组的优化，可以大幅降低空间复杂度，使得算法在处理大规模输入时依然高效。
• 这个问题是动态规划中的经典案例，掌握其解法对于解决更复杂的回文问题具有重要意义。

以上就是最长回文子序列问题的基本思路。

代码实现

Python

Python3代码实现

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        # 创建dp数组
        dp = [[0] * n for _ in range(n)]

        # 单个字符的回文子序列长度为1
        for i in range(n):
            dp[i][i] = 1
        
        # 填充dp数组
        for length in range(2, n + 1):  # 子串长度从2到n
            for i in range(n - length + 1):
                j = i + length - 1  # 右边界
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        
        # 返回整个字符串的最长回文子序列长度
        return dp[0][n - 1]

Python 代码解释

• 初始化：创建一个二维数组 dp 并初始化每个单个字符的回文子序列长度为 1。
• 填充 dp 数组：使用两层循环计算各个子串的回文子序列长度，依据首尾字符的比较进行递推。
• 返回结果：最终返回 dp[0][n-1]，即整个字符串的最长回文子序列长度。

C++

C++代码实现

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        // 创建dp数组
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // 单个字符的回文子序列长度为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 填充dp数组
        for (int length = 2; length <= n; length++) {  // 子串长度从2到n
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;  // 右边界
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        // 返回整个字符串的最长回文子序列长度
        return dp[0][n - 1];
    }
};

C++ 代码解释

• 初始化：创建一个二维 dp 数组并设置每个单个字符的回文子序列长度为 1。
• 动态规划填充：使用双重循环遍历每个可能的子串，根据字符相同与否更新 dp 数组。
• 返回结果：返回 dp[0][n-1]，表示整个字符串的最长回文子序列的长度。

总结:

• 动态规划是解决最长回文子序列问题的有效工具，能够通过状态转移找到最优解。
• 通过合理的状态设计与空间优化，可以在保持效率的前提下大幅度降低空间复杂度。
• 掌握此问题的解决方法，不仅对理解动态规划有很大帮助，也为其他复杂回文问题的处理奠定基础。