动态规划：求解《516. 最长回文子序列》和《1682. 最长回文子序列 II》

动态规划顺序

• i 倒序
• j 顺序，从 i + 1 开始

例题

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

答案

动态规划

var longestPalindromeSubseq = function(s) {
  const n = s.length, dp = Array.from({length: n}, _ => new Uint16Array(n))
  for (let i = n; i--;) {
    dp[i][i] = 1
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
      }
    }
  }
  return dp[0][n - 1]
};

func longestPalindromeSubseq(s string) int {
  n := len(s)
  dp := make([][]int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]int, n)
  }
  for i := n - 1; i >= 0; i-- {
    dp[i][i] = 1
    for j := i + 1; j < n; j++ {
      if s[i] == s[j] {
        dp[i][j] = dp[i + 1][j - 1] + 2
      } else {
        dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
      }
    }
  }
  return dp[0][n - 1]
}
func max (a int, b int) int {
  if a > b {
    return a
  }
  return b
}

1682. 最长回文子序列 II

字符串 s 的某个子序列符合下列条件时，称为“好的回文子序列”： 它是 s 的子序列。 它是回文序列（反转后与原序列相等）。 长度为偶数。 除中间的两个字符外，其余任意两个连续字符不相等。 例如，若 s = "abcabcabb"，则 "abba" 可称为“好的回文子序列”，而 "bcb" （长度不是偶数）和 "bbbb" （含有相等的连续字符）不能称为“好的回文子序列”。 给定一个字符串 s， 返回 s 的最长“好的回文子序列”的长度。

答案

动态规划

增加 1 位，记录上一次状态的回文

var longestPalindromeSubseq = function(s) {
  const n = s.length, dp = Array.from({length: n}, _ => Array.from({length: n}, _ => new Uint8Array(2)))
  for (let i = n; i--;) {
    dp[i][i][0] = 0 // 可省略
    dp[i][i][1] = s.charCodeAt(i) // 可省略
    for (let j = i + 1; j < n; j++) {
      if (s[i] === s[j] && s.charCodeAt(i) !== dp[i + 1][j - 1][1]) {
        dp[i][j][0] = dp[i + 1][j - 1][0] + 2
        dp[i][j][1] = s.charCodeAt(i)
      } else {
        if (dp[i + 1][j][0] > dp[i][j - 1][0]) {
          dp[i][j][0] = dp[i + 1][j][0]
          dp[i][j][1] = dp[i + 1][j][1]
        } else {
          dp[i][j][0] = dp[i][j - 1][0]
          dp[i][j][1] = dp[i][j - 1][1]
        }
      }
    }
  }
  return dp[0][n - 1][0]
};

func longestPalindromeSubseq(s string) int {
  n := len(s)
  dp := make([][][]int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([][]int, n)
    for j := 0; j < n; j++ {
      dp[i][j] = make([]int, 2)
    }
  }
  for i := n - 1; i >= 0; i-- {
    dp[i][i][0] = 0
    dp[i][i][1] = int(s[i])
    for j := i + 1; j < n; j++ {
      if s[i] == s[j] && int(s[i]) != dp[i + 1][j - 1][1] {
        dp[i][j][0] = dp[i + 1][j - 1][0] + 2
        dp[i][j][1] = int(s[i])
      } else {
        if dp[i + 1][j][0] > dp[i][j - 1][0] {
          dp[i][j][0] = dp[i + 1][j][0]
          dp[i][j][1] = dp[i + 1][j][1]
        } else {
          dp[i][j][0] = dp[i][j - 1][0]
          dp[i][j][1] = dp[i][j - 1][1]
        }
      }
    }
  }
  return dp[0][n - 1][0]
}