点击此处返回总目录

【题目】

注意，子序列跟子串是不一样的。子序列是从字符串中取出元素，相对顺序不变，但是可以不挨着。子串肯定是截取一段。

【方法一：记忆化搜索】

假设fun(char[] S , int i , int j) 返回的是串S[i...j]的最长回文子序列。

则如果S[i]==S[j] , 则：fun(S, i , j) = 2+fun(S , i+1 , j-1)

如果不等，则，fun(S , i , j) = max{ fun(S, i+1 , j) ,  fun(S , i , j-1)}

递归写法如下：

很显然，会超时：

因为计算了很多遍重复的。

因此，需要进行改进：将中间结果进行保存。下次计算的时候就不需要重复计算了。这就是记忆化搜索的方法。

代码：

结果：

【方法二：动态规划】

设dp[i][j]为从i到j的字符串，回文子序列的最大长度。

代码：

为什么这么写呢？

首先要心中有这个图。

主对角线是我们自己填进去的。dp[i][i]=1。其他元素我们是用dp[][]式子求的。并没有把次对角线和其他元素分开计算。是因为能够统一写。

首先看次对角线的元素。比如dp[2][3]。如果S[2]==S[3]，则dp[2][3]=dp[3][2]+2。而dp[3][2]虽然没有求，但是是默认值0,这样dp[2][3]=2。如果S[2]!=S[3]，则dp[2][3]=max(dp[3][3], dp[2][2])=1。都是对的。

对于其他元素dp[i][j]。如果S[i]==S[j]，则dp[i][j]=2+dp[i+1][j-1]，用到了那个左小角的元素。如果S[i]!=S[j]，则dp[i][j]=max(dp[i][j-1],dp[i+1][j])，用到了左边和右边的两个元素。

按照我们先下后上，先左后右的顺序，左下、下、左的元素都求出来了。所以肯定能求出dp[i][j]。

结果：

时间复杂度：o(n^2)

虽然只跑出了32ms，但是看17ms的答案也是这么写的。
 

注：

我在看相关的书和博客的时候，有下面一些叫法，感觉都一样：

记忆化搜索 =   记忆递归型的动态规划    =  记忆化递归

动规            =  递推型动态规划

叫法就不纠结了。