2370. Longest Ideal Subsequence
一开始有想到大方向 但做起来有点不顺
没有把dp定义的清楚一点的话写起来就会错东错西
第i轮的dp[c] 定义成走到第i轮的时候 若str[i]==c的话 当时的长度
所以for loop最前面可以更新ans
然后再来更新 以c上下找k的范围里面的dp arr = dp[c]+1 (如果比较大的话)
我第一个错是dp没有initialize成1 会出问题
第二个是更新的时候 我一开始写成dp[idx] = max(dp[idx], dp[s[i]-'a']+1);
这样会把自己重复加 造成c的右半会被误加
简单来说
我好烂
int longestIdealString(string s, int k) {
vector<int> dp(26, 1);
int ans = 0;
for(int i=0; i<s.size(); i++)
{
ans = max(ans, dp[s[i]-'a']);
int cur_cnt = dp[s[i]-'a'];
for(int idx=max((s[i] - 'a') - k, 0); idx<=min((s[i] - 'a') + k, 25);
idx++)
{
dp[idx] = max(dp[idx], cur_cnt+1);
}
}
return ans;
}