516.最长回文子序列

516.最长回文子序列

题目

思路

回文子序列都是动态规划经典题目，用从Carl哥那里学来的动态规划五部曲：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 列举推导dp数组

确定dp数组以及下标的含义

dp[i] [j][i, j]dp[i] [j]

确定递推公式

dp[i] [j] dp[i + 1] [j - 1] + 2

s[i]s[j]s[i]s[j]

dp[i + 1] [j]

dp[i] [j - 1]

dp[i][j] = max(dp[i + 1] [j], dp[i] [j - 1])

dp数组如何初始化

dp[i][j]=1

也就是当i与j相同，一个字符的回文子序列长度就是1。

确定遍历顺序

dp[i][j]i>j

dp[i][j]从下到上，从左到右da，b，c

列举推导dp数组

dp[0][length - 1]

代码

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

for i:=0;i<l;i++{
    for j:=0;j<l;j++{
        if i==j{
            dp[i][j]=1
        }else{
            dp[i][j]=0
        }
    }
}

for i:=l-1;i>=0;i--{
    
    for j:=i+1;j<l;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])
        }
    }
}

return dp[0][l-1]
}

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