推 sustainer123: 我今天看解答 超廢 04/25 22:24
→ DJYOSHITAKA: 其實好像根本不需要i== 04/25 22:24
推 pandix: 你很棒 04/25 22:33
你們是大師
※ 編輯: DJYOSHITAKA (114.137.83.190 臺灣), 04/25/2024 22:36:28
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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.83.190 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714054858.A.1A0.html