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;
}