※ 引述 《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;
}
};