回文子序列都是动态规划经典题目,用从Carl哥那里学来的动态规划五部曲:
dp[i] [j]
:字符串s在[i, j]
范围内最长的回文子序列的长度为dp[i] [j]
.
如果s[i]与s[j]相同,那么dp[i] [j]
= dp[i + 1] [j - 1] + 2
;
如果s[i]与s[j]不相同,说明s[i]
和s[j]
的同时加入 并不能增加[i,j]区间回文子串的长度,那么分别加入s[i]
、s[j]
看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1] [j]
。
加入s[i]的回文子序列长度为dp[i] [j - 1]
。
那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1] [j], dp[i] [j - 1])
;
这里我们使dp[i][j]=1
也就是当i与j相同,一个字符的回文子序列长度就是1。
注意我们二维数组dp[i][j]
的定义,如果i>j
是没有意义的。
从上面图中可以看出如果我们想求dp[i][j]
,那么其他3个必须都是已知的,很明显从上往下遍历是不行的,我们只能让i从最后一个字符往前遍历,j从i的下一个开始遍历,也就是从下到上,从左到右
的顺序,这样才能保证计算d
的时候,a,b,c
的值都已经计算过了。
列举完毕后,发现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 }