516.最大回文子序列

动态规划

dp[i][j] 用来记录从i到j位置的字符串的最大回文子序列长度。

dp[i][i] 都为1。

状态转移时考虑最左和最右元素是否相等，相等则转移至 dp[i+1][j-1] ，否则考虑 dp[i+1][j] 和 dp[i][j-1] 的较大者 。

注意遍历时，i从右边开始，可以保证每个子问题都计算过了。

时间复杂度：O(N^2)
空间复杂度：O(N^2)

func longestPalindromeSubseq(s string) int {
	// s[i] != s[j]
	// dp[i][j] = max(dp[i][j-1], dp[i+1][j])
	// s[i] == s[j]
	// dp[i][j] = dp[i+1][j-1] + 2

	dp := make([][]int, len(s))
	for i := 0; i < len(s); i++ {
		dp[i] = make([]int, len(s))
		dp[i][i] = 1
	}

	for i := len(s) - 1; i >= 0; i-- {
		for j := i + 1; j < len(s); j++ {
			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])
			}
			// fmt.Printf("dp[%v][%v], %v\n", i, j, dp[i][j])
		}
	}

	return dp[0][len(s)-1]
}

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