leetcode516. 最长回文子序列-附动态规划状态图

leetcode516. 最长回文子序列-附动态规划状态图

四月 11, 2020

leetcode516. 最长回文子序列

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:
“bbbab”
输出:
4
一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:
“cbbd”
输出:
2

本题和

回文子串
最长回文子串
思路类似。
用 dp[i][j] 表示 i~j 内回文子序列的最长长度。

找出当前的状态怎么处理

  • 当 s[i] == s[j] 时，只需用 dp[i+1][j-1] 加上2就是当前的最大长度，因为 dp[i+1][j-1] 已经含有回文子序列（上面定义），所以再加上2就行。(如果 i+1 < j-1 ，也就是子序列长度为2，需要特殊处理)
  • 如果 s[i] != s[j] 。需要找出 i~j 里面最大的。而如果子序列最长，也就是 i-j 越大，他们的dp也会越大，因为字母多。所以只需要取 i-j-1 长度的序列就行。在 i~j 序列中，这样的序列有两个 i+1~j 和 i~j-1 ，取这两个当中最大的。 dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);

    填表

    画出表格，看看应该怎么填表。
    在这里插入图片描述
    根据式子dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);，在填(1,3)时候会用到他的左面和下面。
    在这里插入图片描述
    所以要先填不能用到左面和下面的点，也就是说当前填的点必须用到填过的，不能用到没填过的。
    填表的方式应该很多，我选择的是从最后一行开始向右遍历，再逐步向上遍历。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public int longestPalindromeSubseq(String s) {
          int n = s.length();
          int max = 1;
          int[][] dp = new int[n][n];
          for (int  i = n - 1; i >= 0; i--) {
              dp[i][i] = 1;
              for (int j = i + 1; j < n; j++) {
                  if (s.charAt(i) == s.charAt(j)) {
                      if (i + j == 1) {
                          dp[i][j] = 2;
                      } else {
                          dp[i][j] = dp[i + 1][j - 1] + 2;
                      }
                  } else{
                      dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
                  }
                  
                  max = Math.max(max, dp[i][j]);
              }
          }
          
          return max;
      }
    leetcode 77/100