lc1653
dp
/*
输入：s = "aababbab"
输出：2
*/
class Solution {
public:
int minimumDeletions(string s)
{
int n=s.size();
vector<vector<int>> dp(n+1,vector(2,0));
for(int i=1;i<=n;i++)
{
if(s[i-1]=='a')
{
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1]+1;//turn b
}
else
{
dp[i][0]=dp[i-1][0]+1;
dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
}
}
return min(dp[n][0],dp[n][1]);
}
};
单变量记录优化
class Solution {
public:
int minimumDeletions(string s) {
int f = 0, cnt_b = 0;
for (char c : s) {
if (c == 'b')
cnt_b++; // f 值不变
else
f = min(f + 1, cnt_b);
}
return f;
}
};
