[Day10]-[动态规划] 最长回文子序列

输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。

输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。

func longestPalindromeSubseq(s string) int {	var solution func(str string) int // 解决方案	var max func(x, y int) int        // 取最大值	max = func(x, y int) int {		if x > y {			return x		}		return y	}	solution = func(str string) int {		length := len(str)            // 字符串长度		dp := make([][]int, length)   // dpTable		for i := 0; i < length; i++ { // 准备基础数据 对角线都是1			dp[i] = make([]int, length)			dp[i][i] = 1		}        // 倒序遍历(从下到上，从左到右) 从最下方 倒数第二行 最后一列开始填充		for i := length - 2; i >= 0; i-- { 			for j := i + 1; j < length; j++ {				if str[i] == str[j] { // 如果相等 则回文数+2					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][length-1] // 终止条件就是整个字符的最大回文数	}
    return solution(s)}