Longest Palindromic Subsequence

Longest Palindromic Subsequence

题目描述

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:

"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb".

思路：

• 动态规划，子串长i，起始索引为j的字串。最大子序列问题，动态规划串长和起始索引。
• 由于是找序列，动规结果直接就是“子串的最大回文串长度”。
• 对于dp[i][j]，两边相等用则为2+dp[i-2][j+1]，否则取dp[i-1][j-1]和dp[i-1][j+1]的最大值。解释：两边成对可以用去掉两边的结果计算。如果两边不成对，无论中间为奇数或偶数，最多只能“补充”一个字符。所以在补充一个字符的结果中选最大的。
• 填充顺序，i从小大到填，逐行填充第i行。
• 最终结果dp[n][0]

解：

package main

import "fmt"

func longestPalindromeSubseq(s string) int {
    sSlice := []rune(s)
    dp := make([][]int,len(sSlice)+1)
    for idx,_ := range dp{
        dp[idx] = make([]int,len(sSlice))
    }
    for i:= 0;i< len(sSlice);i++{
        dp[1][i] = 1
    }

    for i := 2; i<len(sSlice)+1;i++  {
        for j := 0; j<(len(sSlice)-i+1);j++  {
            if sSlice[j]== sSlice[i+j-1] {
                dp[i][j] = dp[i-2][j+1]+2
            }else {
                switch dp[i-1][j] > dp[i-1][j+1] {
                case true:
                    dp[i][j] = dp[i-1][j]
                case false:
                    dp[i][j] = dp[i-1][j+1]
                }
            }
        }
    }
    fmt.Println(dp)
    return dp[len(sSlice)][0]
}

func main()  {
    s := "bbbab"
    res := longestPalindromeSubseq(s)
    fmt.Print(res)
}