算法1:动态规划
/*
dp[i][j] = 我们处理了原字符串中的前i个字符(i 从1开始编号),并且【处理过的字符串】的
最后一个字符为j( j = 0 .. 25)的最小删除代价
// 转移:
删除第i个字符:dp[i][j] = dp[i - 1][j] + cost[i]
不删除:dp[i][s[i]] = min(dp[i - 1][j != s[i]] )
*/
class Solution {
public:
int minCost(string s, vector<int>& cost) {
int n = cost.size();
vector<vector<int>> f(n + 1,vector<int>(26));
// 边界f[i][k] = 0;
for(int i=1;i<=n;i++)
{
// 删
for(int j = 0;j < 26;j ++ )
f[i][j] = f[i-1][j] + cost[i - 1];
// 不删
int t = s[i-1] - 'a';
for(int j = 0; j< 25;j ++)
if(j != t)
f[i][t] = min(f[i][t],f[i-1][j]);
}
int res = 1e9;
for(int i=0;i<26;i++) res = min(res,f[n][i]);
return res;
}
};
算法2:双指针
依次找出长度 > 1
的子串,先把这一段全部删掉,再补上这一段中的最大值,即可得把这一段删得不相邻的最小代价
class Solution {
public:
int minCost(string s, vector<int>& cost) {
s += '@'; // 哨兵
int res = 0;
for(int i=0 , j = 0;i < s.size(); )
{
while(j < s.size() && s[j] == s[i]) j ++;
if(j - i > 1)
{
int max_cost = 0; // 维护这一段中的最大值,后面补回来
while(i < j)
{
res += cost[i];
max_cost = max(max_cost,cost[i]);
i ++ ;
}
res -= max_cost;
}
else i ++;
}
return res;
}
};