题目内容

给定一个只含小写字母的字符串$s$ , $k$阶完美子序列$t$的定义是：$t$是字符串$s$ 的一个子序列.并且$t$中任意一个相邻的字符在字符表中距离相差不过$k$.现在塔子哥需要你求出最长的k阶完美子序列

说明：

题解：字符串DP

定义$f[i][j]$$表示前$i$个字母以字母$$j$结尾的最长子序列长度

对于前$i$个字母

• 如果不选择第$i$个字母，则对于任意$0\le j\le 2$，都有$f[i][j]=f[i-1][j]$
• 如果选择第$i$个字母，先把当前字母映射到$[0,25]$(x=s[i]-'a')，然后开始枚举所有$x-k\le j \le x+k$

更新$f[i][x]=max(f[i][x],f[i-1][j]+1)$