dp-＞单变量记录优化

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;

}

};