Leetcode Link: 516. 最长回文子序列 - 力扣（LeetCode）
题目
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
从暴力递归到动态规划
本题属于范围尝试模型
暴力递归
对于在字符串 s 的[L.. R]范围内（含端点）的最长回文子串，其问题可以分解成如下四种情况
- (L × R × ) 回文子串一定不以 L 开头，同时一定不以 R 结尾
- (L √ R × ) 回文子串一定以 L 开头，同时一定不以 R 结尾
- (L × R √ ) 回文子串一定不以 L 开头，同时一定以 R 结尾
- (L √ R √ ) 回文子串一定以 L 开头，同时一定以 R 结尾—> 有前提条件：必须
s[L]==s[R]才可以
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
return self.process(s, 0, len(s)-1)
def process(self, s, L, R):
# 注意base case 不能只写第一个，当L==R-1时候，情况1下一步会跳过这个base case
if L == R:
return 1
if L > R:
return 0
# 区间范围类问题，根据区间端点分类讨论
p1 = self.process(s, L+1, R-1) # 回文一定不以L和R开始和结尾
p2 = self.process(s, L+1, R) # 回文一定以R结尾，一定不以L开头
p3 = self.process(s, L, R-1) # 回文一定以L开头，但一定不以R结尾
p4 = 0
if s[L] == s[R]:
p4 = 2 + self.process(s, L+1, R-1) # 回文一定以L开头同时以R结尾
return max(p1,p2,p3,p4)代码中的细节
情况 1 不必多说 情况 2、3 为啥不+1，表示”确定的开头或者结尾”？——因为早晚会往下递归，在下面的某一个子问题中的情况 4 里加上该位置 情况4：前面说到有前提条件，如果L和R都是回文子串的开头结尾，那就要把这个2加上。
[! hint]- 老师代码中的区别 老师代码中的第二个 base case 是
if s[L]==s[R-1]:return 2，最后的作用和我的一样。 可能写dp的时候条件判断更简单。
动态规划
根据暴力递归改写成动态规划
- 确定dp表的大小，在本题中，显然是2维dp，分别表示L和R，范围都是[0, len(s)-1]
- 根据base case填写初始值，有一些base case可能超出了表的范围，需要在填表的时候利用
if来考虑 - 根据暴力递归中寻找一般情况下的依赖关系，确定填表的顺序，本题中是按照对角线填表。
- 确定返回值在表中的位置。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
# 根据暴力递归研究其依赖关系，发现需要对角线填写
startR = 1 # L==R的主对角线已经填写完了
while(startR < len(s)):
R = startR
L = 0
while(R < len(s)):
# L==R or L > R 的条件已经隐含在我的循环中了
p1 = dp[L+1][R-1]
p2 = dp[L][R-1]
p3 = dp[L+1][R]
p4 = 0
if s[L] == s[R]:
p4 = dp[L+1][R-1]+2
dp[L][R] = max(p1, p2, p3, p4)
L += 1
R += 1
startR += 1
return dp[0][len(s)-1]学习本代码中按照对角线填表的方式
确定起点列，赋值后列和行都++。
动态递归-状态压缩
只有确定了位置依赖关系（空间关系）才有可能进一步优化，所以一定要推。 这道题还算是小优化，会有那种优化非常明显的。
本题中，一般情况下一个格子依赖于其左、左下、下的位置，即
这样看不直观，我们画出两个先后填写的位置(1,2)和其中一个依赖位置(3)，
可以看到，3 位置的格子一定不小于 (3 左，3 下)，同时，3 下等价于 2 左下，3 本身等价于 2 左
据此，我们知道 2>=2 左=3>=3 下=2 左下。
所以，我们省掉一个位置依赖，即只依赖左(p2)、下(p3)，还有一个p4。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
# 根据暴力递归研究其依赖关系，发现需要对角线填写
startR = 1 # L==R的主对角线已经填写完了
while(startR < len(s)):
R = startR
L = 0
while(R < len(s)):
# L==R or L > R 的条件已经隐含在我的循环中了
# 优化掉p1
p2 = dp[L][R-1]
p3 = dp[L+1][R]
p4 = 0
if s[L] == s[R]:
p4 = dp[L+1][R-1]+2
dp[L][R] = max(p2, p3, p4)
L += 1
R += 1
startR += 1
return dp[0][len(s)-1]启发和联系
范围尝试模型，主要思想是讨论一个范围的端点选取的情况来对问题进行分解