> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0516_longest_palindromic_subsequence/slt.md).

# slt

先来看看暴力破解的时间复杂度。

首先，n 个元素的 set 有 sub-set 个数为：$2^n$ n 个元素的 sub-sequence 个数也是 $2^n$。因为集合是无序的，我们取 sub-set 中按原来顺序排的个数，和集合中随变排的个数，这两个个数是一样的。

所以，暴力破解一般是不行的。遇到 sub-sequence 的问题一般要想到 DP

顺便，看看长度为 n 的字符串的子串。这个就比较简单了，长度为 1 的有 n 个，长度为 n 的有 n-1 个，...，长度为 n - 1 的有 2 个，长度为 n 的有一个。所以即是求 $$

$ \sum\limits\_{i=1}^{n} = n \* (n-1) / 2 $

## Solution1 DP

* 时间复杂度 $O(n^2)$
* 空间复杂度 $O(n^2)$
* 状态 f\[i]\[j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少
* 转移方程 如果 s 的第 i 个字符和第 j 个字符相同的话，则有 f\[i]\[j] = f\[i+1]\[j-1] + 2 如果 s 的第 i 个字符和第 j 个字符不同的话，f\[i]\[j] = max(f\[i+1]\[j], f\[i]\[j-1]) 遍历顺序：i 从后往前，j 从 i+1 往后。
* 初始化 f\[i]\[i] = 1
* 结果 f\[0]\[N-1]