最长回文子序列的长度问题（状态压缩优化版本）
字数 2340 2025-12-04 04:27:27

最长回文子序列的长度问题（状态压缩优化版本）

题目描述
给定一个字符串 s，求其最长回文子序列（Longest Palindromic Subsequence, LPS）的长度。回文子序列是通过删除原字符串中的某些字符（也可以不删除）而不改变剩余字符的相对顺序得到的一个序列，且该序列正读反读相同。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb"，长度为 4。要求使用动态规划求解，并进一步优化空间复杂度至 O(n)。

解题思路

  1. 基本区间DP定义

    • 定义 dp[i][j] 表示字符串 s[i..j] 的最长回文子序列长度。
    • 初始条件：当 i == j 时，dp[i][j] = 1（单个字符本身就是回文）。
    • 状态转移方程：
      • 若 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2。
      • 若 s[i] != s[j]，则 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
    • 最终答案：dp[0][n-1]。

  2. 空间优化挑战

    • 基本DP需要 O(n²) 空间，但观察状态转移发现：计算 dp[i][j] 时仅依赖下一行（i+1）和同一行左侧（j-1）的值。
    • 优化思路：使用一维数组 dp[j] 代替二维数组，按行从下往上、每行从左往右更新。

逐步推导

步骤1：基本DP填表示例（以 s = "bbbab" 为例）

  • 初始化：所有 i == j 的格子为 1。
  • 填表顺序：按区间长度 L 从 2 到 n 遍历。
0 1 2 3 4
0 b 1 2 2 3 4
1 b - 1 2 2 3
2 b - - 1 1 3
3 a - - - 1 1
4 b - - - - 1

步骤2：空间优化策略

  • 使用一维数组 dp 表示当前行（第 i 行）的结果。
  • 额外变量 prev 保存 dp[i+1][j-1] 的值（即上一轮计算中 dp[j-1] 的旧值）。
  • 更新顺序：
    1. 外层循环 i 从 n-1 到 0 倒序（从最后一行往上）。
    2. 内层循环 j 从 i+1 到 n-1 正序。
    3. 在更新 dp[j] 前，用 temp 保存当前 dp[j]（即下一行的 dp[j]），用于后续计算 prev。

步骤3：优化后的状态转移

  • 若 s[i] == s[j]：
    • 如果 j == i+1，直接赋值为 2（相邻字符相同）。
    • 否则，dp[j] = prev + 2（prev 即 dp[i+1][j-1] 的旧值）。
  • 若 s[i] != s[j]：dp[j] = max(dp[j], dp[j-1])（dp[j] 是下一行的值，dp[j-1] 是当前行已更新的值）。
  • 每轮内层循环结束时，更新 prev = temp（为下一轮 j+1 准备）。

步骤4：示例演示（s = "bbbab"）
初始：dp = [1,1,1,1,1]（对应 i=n-1 时的初始值）。

  • i=3（字符 a）：

    • j=4：s[3]!=s[4]，dp[4]=max(dp[4],dp[3])=max(1,1)=1。
    • 更新后 dp=[1,1,1,1,1]。

  • i=2（字符 b）：

    • j=3：s[2]!=s[3]，dp[3]=max(1,1)=1。
    • j=4：s[2]==s[4]，prev=dp[3]的旧值=1，dp[4]=prev+2=3。
    • 更新后 dp=[1,1,1,1,3]。

  • i=1（字符 b）：

    • j=2：s[1]==s[2]，prev=dp[1]的旧值=1，dp[2]=1+2=3？
      • 纠正：j=2 时，j-i=1，直接赋 2（相邻相同字符）。
    • j=3：s[1]!=s[3]，dp[3]=max(dp[3],dp[2])=max(1,2)=2。
    • j=4：s[1]==s[4]，prev=dp[3]的旧值=1，dp[4]=1+2=3？
      • 纠正：prev 应为 i=1,j=4 时 dp[3] 在下一行（i=2）的值，即 1，正确。
    • 更新后 dp=[1,1,2,2,3]。

  • i=0（字符 b）：

    • j=1：相邻相同，dp[1]=2。
    • j=2：s[0]==s[2]，prev=dp[1]的旧值=1，dp[2]=1+2=3？
      • 纠正：j=2 时，prev 取下一行 dp[1] 的旧值（即 i=1 时 dp[1]=1），正确。
    • j=3：s[0]!=s[3]，dp[3]=max(2,3)=3。
    • j=4：s[0]==s[4]，prev=dp[3]的旧值=2，dp[4]=2+2=4。
    • 最终 dp[4]=4。

复杂度分析

  • 时间复杂度：O(n²)。
  • 空间复杂度：O(n)。

关键点

  • 优化时需注意 prev 的保存时机，确保它代表 dp[i+1][j-1]。
  • 相邻字符（j=i+1）需单独处理。

此方法将经典区间DP的空间消耗降低，适用于大规模字符串处理。

最长回文子序列的长度问题（状态压缩优化版本） 题目描述 给定一个字符串 s ，求其最长回文子序列（Longest Palindromic Subsequence, LPS）的长度。回文子序列是通过删除原字符串中的某些字符（也可以不删除）而不改变剩余字符的相对顺序得到的一个序列，且该序列正读反读相同。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb" ，长度为 4。要求使用动态规划求解，并进一步优化空间复杂度至 O(n)。 解题思路 基本区间DP定义 定义 dp[i][j] 表示字符串 s[i..j] 的最长回文子序列长度。 初始条件：当 i == j 时， dp[i][j] = 1 （单个字符本身就是回文）。 状态转移方程： 若 s[i] == s[j] ，则 dp[i][j] = dp[i+1][j-1] + 2 。 若 s[i] != s[j] ，则 dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 。 最终答案： dp[0][n-1] 。 空间优化挑战 基本DP需要 O(n²) 空间，但观察状态转移发现：计算 dp[i][j] 时仅依赖下一行（ i+1 ）和同一行左侧（ j-1 ）的值。 优化思路：使用一维数组 dp[j] 代替二维数组，按行从下往上、每行从左往右更新。 逐步推导 步骤1：基本DP填表示例（以 s = "bbbab" 为例） 初始化：所有 i == j 的格子为 1。 填表顺序：按区间长度 L 从 2 到 n 遍历。 | | 0 | 1 | 2 | 3 | 4 | |-----|-----|-----|-----|-----|-----| | 0 b | 1 | 2 | 2 | 3 | 4 | | 1 b | - | 1 | 2 | 2 | 3 | | 2 b | - | - | 1 | 1 | 3 | | 3 a | - | - | - | 1 | 1 | | 4 b | - | - | - | - | 1 步骤2：空间优化策略 使用一维数组 dp 表示当前行（第 i 行）的结果。 额外变量 prev 保存 dp[i+1][j-1] 的值（即上一轮计算中 dp[j-1] 的旧值）。 更新顺序： 外层循环 i 从 n-1 到 0 倒序（从最后一行往上）。 内层循环 j 从 i+1 到 n-1 正序。 在更新 dp[j] 前，用 temp 保存当前 dp[j] （即下一行的 dp[j] ），用于后续计算 prev 。 步骤3：优化后的状态转移 若 s[i] == s[j] ： 如果 j == i+1 ，直接赋值为 2（相邻字符相同）。 否则， dp[j] = prev + 2 （ prev 即 dp[i+1][j-1] 的旧值）。 若 s[i] != s[j] ： dp[j] = max(dp[j], dp[j-1]) （ dp[j] 是下一行的值， dp[j-1] 是当前行已更新的值）。 每轮内层循环结束时，更新 prev = temp （为下一轮 j+1 准备）。 步骤4：示例演示（s = "bbbab"） 初始： dp = [1,1,1,1,1] （对应 i=n-1 时的初始值）。 i=3 （字符 a ）： j=4： s[3]!=s[4] ， dp[4]=max(dp[4],dp[3])=max(1,1)=1 。 更新后 dp=[1,1,1,1,1] 。 i=2 （字符 b ）： j=3： s[2]!=s[3] ， dp[3]=max(1,1)=1 。 j=4： s[2]==s[4] ， prev=dp[3]的旧值=1 ， dp[4]=prev+2=3 。 更新后 dp=[1,1,1,1,3] 。 i=1 （字符 b ）： j=2： s[1]==s[2] ， prev=dp[1]的旧值=1 ， dp[2]=1+2=3 ？ 纠正： j=2 时， j-i=1 ，直接赋 2（相邻相同字符）。 j=3： s[1]!=s[3] ， dp[3]=max(dp[3],dp[2])=max(1,2)=2 。 j=4： s[1]==s[4] ， prev=dp[3]的旧值=1 ， dp[4]=1+2=3 ？ 纠正： prev 应为 i=1,j=4 时 dp[3] 在下一行（i=2）的值，即 1，正确。 更新后 dp=[1,1,2,2,3] 。 i=0 （字符 b ）： j=1：相邻相同， dp[1]=2 。 j=2： s[0]==s[2] ， prev=dp[1]的旧值=1 ， dp[2]=1+2=3 ？ 纠正： j=2 时， prev 取下一行 dp[1] 的旧值（即 i=1 时 dp[1]=1 ），正确。 j=3： s[0]!=s[3] ， dp[3]=max(2,3)=3 。 j=4： s[0]==s[4] ， prev=dp[3]的旧值=2 ， dp[4]=2+2=4 。 最终 dp[4]=4 。 复杂度分析 时间复杂度：O(n²)。 空间复杂度：O(n)。 关键点 优化时需注意 prev 的保存时机，确保它代表 dp[i+1][j-1] 。 相邻字符（ j=i+1 ）需单独处理。 此方法将经典区间DP的空间消耗降低，适用于大规模字符串处理。