贪心
简单证明下:
1.我们把问题集合划分为2类,要翻转的和不反转的
2.重点是翻转的,翻转需要将前i - 1
个字符翻转或者将第i个以后的字符翻转(当前第i - 1
和第 i
个字符不同)
3.这样前面的字符变成和第i
个字符相同或者将第i个以后的字符和前面一样,将其转化成和答案相同的集合,至于代价取最小值就可 min(i + 1, n - 1 - i)
下面看代码
C++ 代码
class Solution {
public:
long long minimumCost(string s) {
long long res = 0;
int n = s.size();
for (int i = 0; i < n - 1; i ++ )
if (s[i] != s[i + 1])
res += min(i + 1, n - i - 1);
return res;
}
};