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]