class Solution {
public:
//本题同股票交易(可多次交易)问题,异曲同工
int minimumOperations(string leaves) {
vector<int> dp(3);
//dp[0]:将当前叶子及之前叶子全部变红的最小替换次数
//dp[1]:将现在以及前面叶子变为红+黄状态的最小替换次数
//dp[2]:将现在及前面叶子变成红+黄+红状态的最小替换数
dp[0] = 0; dp[1] = 0x3f3f3f3f; dp[2] = 0x3f3f3f3f;//初始化
for(int i = 0; i < leaves.size(); i++) {
int dp0 = dp[0], dp1 = dp[1], dp2 = dp[2];
//记录旧的状态值,它们会变化
if(leaves[i] == 'r') {
dp[0] = dp0;
if(i > 0) dp[1] = min(dp0 + 1, dp1 + 1);
if(i > 1) dp[2] = min(dp2, dp1);
}else {
dp[0] = dp0 + 1;
if(i > 0) dp[1] = min(dp1, dp0);
if(i > 1) dp[2] = min(dp2 + 1, dp1 + 1);
}
}
return dp[2];
}
};