leetcode 1653. 使字符串平衡的最少删除次数

Problem: 1653. 使字符串平衡的最少删除次数动态规划的呢dp[i]表示前i个字符balance的最小删除次数dp[0]0初始化若l1, s[l-1]a’则dp[l] 0;递推公式是若s[i-1]‘b’此时可以保留bdp[i] dp[i-1]若s[i-1]‘a’此时要么删除这个adp[i] dp[i-1]1要么保留这个a删除前面的所有b也就是 dp[i] min(dp[i-1] 1, prefix[i]);Codeclass Solution { public: int minimumDeletions(string s) { int n s.size(), l 1; vectorint prefix{0}, dp(n1, INT_MAX/100); for(char c : s) { prefix.push_back(prefix.back() (int)(cb)); } dp[0] 0; while(l n s[l-1]a) dp[l] 0; for(int i l; i n; i) { if(s[i-1] b) dp[i] dp[i-1]; else { dp[i] min(dp[i-1] 1, prefix[i]); } } return dp[n]; } };