最长回文子序列

最长回文子序列

leetcode 链接

思路：

1. 确定 dp 数组定义, dp[i][j] 表示 s[i,j]子串是否为回文串

2. 初始化 dp 数组, 默认为 0, dp[i][i] = 1

3. 确定遍历方向, 从后往前遍历

4. 确定转移方程, 如果 s[i] === s[j], 则为 dp[i+1][j-1] + 2, 如果 s[i] !== s[j], 则为 Math.max(dp[i][j-1], dp[i+1][j])

5. 返回 dp[0][s.length-1]

typescript 解法

function longestPalindromeSubseq(s: string): number {
  let dp = Array.from({ length: s.length }, () => new Array(s.length).fill(0));

  for (let i = 0; i < s.length; i++) {
    dp[i][i] = 1;
  }

  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = i + 1; j < s.length; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
      }
    }
  }
  return dp[0][s.length - 1];
}

go 解法

func longestPalindromeSubseq(s string) int {
    // dp[i][j] 表示字符s下标为i和j的最长回文子序列长度为dp[i][j]
    lenS := len(s)
    dp := make([][]int, lenS)
    for i := 0; i < lenS; i ++{
        dp[i] = make([]int, lenS)
        for j := 0; j < lenS; j ++ {
            if i == j {
                dp[i][j] = 1
            } else {
                dp[i][j] = 0
            }
        }
    }

    for i := lenS - 1; i >= 0; i -- {
        for j := i + 1; j < lenS; j ++ {
            if string(s[i]) == string(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][lenS - 1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}