※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
:
: 2370. Longest Ideal Subsequence
: https://leetcode.com/problems/longest-ideal-subsequence/description
: 给你一个字串s和一个数字k，找出一个子序列满足相邻的字符距离不相差超过k个，返回
: 最长是多长(note:a和z距离25而不是1)。
思路:
第一眼看到
我就想n^2了
然后想了一阵子
发现如果出现两个a
后面的那个a完全可以继承前面a的所有东西
然后要找最新的长度的话
只要看那个字母-k+k
产生出来的最后面的那个长度就好了
反正
就是用a~z的字母跟s字串dp
姆咪
class Solution {
public:
int longestIdealString(string s, int k)
{
int len = s.size();
vector<int> paper(26 , 0);
int now = 0;
for(int i = 0 ; i < len ; i ++)
{
now = 0;
int sn = s[i]-'a';
for(int j = max(0,sn-k) ; j <= min(25,sn+k) ; j ++)
{
now = max(now , paper[j]);
}
paper[sn] = now + 1;
}
int res = 0;
for(int i = 0 ; i < 26 ; i ++)
{
res = max(res,paper[i]);
}
return res;
}
};