最长回文子序列（IPS）

---

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度

• 递归解法：

1.如果str的最后一个元素和第一个元素是相同的，则有：lps(0,n-1)=lps(1,n-2)+2；例如字符串序列“AABACACBA”，第一个元素和最后一个元素相同，其中lps(1,n-2)表示红色部分的最长回文子序列的长度；

2.如果str的最后一个元素和第一个元素是不相同的，则有：lps(0,n-1)=max(lps(1,n-1),lps(0,n-2))；例如字符串序列“ABACACB”，其中lps(1,n-1)表示去掉第一元素的子序列，lps(0,n-2)表示去掉最后一个元素的子序列。

class Solution:
    def Circle(self,s,left,right):
        if(left==right):
            return 1
        elif(left>right):
            return 0
        else:
            if(s[left]!=s[right]):
                return max(self.Circle(s,left,right-1),self.Circle(s,left+1,right))
            else:
                return self.Circle(s,left+1,right-1)+2
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s)==1:
            return 1
        if s[0]==s[-1]:
            return self.Circle(s,1,len(s)-2)+2
        else:
            return max(self.Circle(s,1,len(s)-1),self.Circle(s,0,len(s)-2))
        return maxnum*2

---

• 动态规划：

定义：d[i][j] 表示最大的回文字符串的长度

初始化：d[i][i] = 1 其他均为0，通过保持

i从length自高向低遍历，因为[i+1][j-1]需要上一级的结果，只求[i,j]范围内的解。i+1>j-1时因为j>=i+1，所以会落在(i+1,i)上，该点位于下半侧为0。

考虑两种情况：s[i] == s[j] d[i+1][j-1]+2，s[i] != s[j] max(d[i+1][j], d[i][j-1])

如果[3][4]->[4][3]，因为位于下半边的值默认为0，所以不会影响结果

最终结果： d[1][length] 其中n是字符串的长度

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        length=len(s)
        dp=[[0]*(length+1) for i in range(length+1)]
        for i in range(1,length+1):
            dp[i][i]=1
        for i in range(length,0,-1):
            for j in range(i+1,length+1):
                if s[i-1]==s[j-1]:
                    # 因为要求[i+1]所以必须得到上一层的解，所以要从高层length往底层1遍历
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])
        return dp[1][length]

---

状态压缩改进：

在dp[i+1][j-1]被覆盖之前用一个临时变量 temp 把它存起来，并把这个变量的值保留到计算 dp[i][j] 的时候

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if len(s)==1:
            return 1
        dp=[0 for i in range(len(s))]
        for i in range(len(s)-2,-1,-1):
            dp[i]=1
            pre=0
            for j in range(i+1,len(s)):
                temp = dp[j];
                if s[i]==s[j]:
                    dp[j]=pre+2
                else:
                    dp[j]=max(dp[j-1],dp[j])
                pre=temp
        return dp[-1]