2021-02-08：给定一个字符串str，请问这个字符串的最长回文子序列长度是多少？

package main

import "fmt"

func main() {
    ret := longestPalindromeSubseq("bbbabbbb")
    fmt.Println("递归：", ret)
    ret = longestPalindromeSubseq2("bbbabbbb")
    fmt.Println("动态规划：", ret)
}

//递归
func longestPalindromeSubseq(s string) int {
    return process(s)
}
func process(s string) int {
    sLen := len(s)
    if sLen == 0 {
        return 0
    }
    if sLen == 1 {
        return 1
    }
    ret1 := process(s[1 : sLen-1])
    ret2 := 0
    ret3 := 0
    if s[0] != s[sLen-1] {
        ret2 = process(s[0 : sLen-1])
        ret3 = process(s[1:sLen])
    } else {
        ret1 += 2
    }
    ret := getMax(ret1, ret2)
    ret = getMax(ret, ret3)
    return ret
}

//动态规划
func longestPalindromeSubseq2(s string) int {
    sLen := len(s)
    if sLen == 0 {
        return 0
    }
    if sLen == 1 {
        return 1
    }
    dp := make([][]int, sLen)
    for i := 0; i < sLen; i++ {
        dp[i] = make([]int, sLen)
    }
    for i := 0; i < sLen-1; i++ {
        dp[i][i] = 1
        if s[i] == s[i+1] {
            dp[i][i+1] = 2
        } else {
            dp[i][i+1] = 1
        }
    }
    for L := sLen - 3; L >= 0; L-- {
        for R := L + 2; R < sLen; R++ {
            dp[L][R] = getMax(dp[L][R-1], dp[L+1][R])
            if s[L] == s[R] {
                dp[L][R] = getMax(dp[L][R], 2+dp[L+1][R-1])
            }
        }
    }
    return dp[0][sLen-1]
}

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