原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个具体数值，代表最长长度
1.2 题目背景、允许、禁止与限制
背景：有一个长度为 lenlenlen 的字符串 SSS
允许：选择其中的一个子序列，使得这个子序列是回文字符串
禁止：
限制：最终要求求出符合要求子序列的最长长度
> 子序列的定义是：字符串 AAA 再删除若干个不一定连续的字符后成为 BBB，就称字符串 BBB 是字符串 AAA 的子序列
1.3 题目数据范围与猜测
3≤len≤1000⟶O(n2)3 \le len \le 1000 \longrightarrow O(n^2)3≤len≤1000⟶O(n2)
1.4 一句话概括题意
有一个字符串，选择其中的一个子序列，使得这个子序列是回文字符串，求这个子序列长度最大能是多少
2 题目破题推导
> 注：以下七种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
2.3 以终为始、以始为终
2.4 数学
2.5 分情况考虑
既然这题已经有了一个关键信息“回文”
那么思考一下回文的条件：
如果 Si=SjS_i=S_jSi =Sj ，则区间 [i+1,j−1][i+1,j-1][i+1,j−1] 中的最长回文子序列长度 +2+ 2+2 就是到目前为止的最长回文子序列长度（注意因为这里是“子序列”所以无需考虑区间 [i+1,j−1][i+1,j-1][i+1,j−1] 的回文情况）
否则只能是从区间 [i+1,j][i+1,j][i+1,j] 和 [i,j−1][i,j-1][i,j−1] 的较大值即可
2.6 手动推导
2.7 边界测试
3 模型匹配
先提取关键词：时刻求取当前最小值、区间
是 区间动态规划\huge{区间动态规划}区间动态规划
4 具体方案
4.1 动态规划定义（重点）
首先，先建立 dp 数组
设置 dpij{dp_i}_jdpi j 代表区间 [i,j][i,j][i,j] 范围内最长回文子序列长度
4.2 初始化
求最小值，所以dp数组每一项都设为大值
但是一格一定是回文，因此对于每个 i(1≤i≤n)i (1 \le i \le n)i(1≤i≤n)，都要将 dpii{dp_i}_idpi i 设置为 111
4.3 状态转移方程
我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）
4.4 答案求取
dp1len{dp_1}_{len}dp1 len
5 最终代码（禁止抄袭，仅用于参考）
