道9.4 第三题：一个仅由r、'e、d组成的字符串,每次操作可以将一个r变成e,或者e'变成d,或者d变成r。最终字符串任意相邻字符都不相等.最少要操作多少次？？C++实现

这个问题是一个经典的动态规划问题，通常被称为“红绿灯”问题或者“零一背包”的变种。目标是通过最少的操作次数，使得字符串满足每个相邻字符都不相同。你可以使用动态规划的状态转移方程来解决。

设dp[i][j]表示从字符串前i个字符中选择，使得最后结果字符串中第i个字符和第i+1个字符不相同的最小操作次数。对于状态转移：

- 如果s[i] != s[i+1]，那么不需要做任何操作，dp[i][j] = dp[i-1][j]；
- 如果s[i] == 'r' && s[i+1] == 'e'，需要将'r'变为'e'，dp[i][j] = dp[i-1][j] + 1；
- 同理，如果s[i] == 'e' && s[i+1] == 'd' 或者 s[i] == 'd' && s[i+1] == 'r'，分别需要一次操作，dp[i][j] = dp[i-1][j] + 1。

初始状态dp[0][j] = 0，因为空字符串已经满足条件。

以下是简单的C++代码实现：

#include <iostream>
using namespace std;

int minOperations(string s) {
    int n = s.size();
    if (n <= 1) return 0;
    
    int dp[n][2]; // dp[i][0]: e or d at i, dp[i][1]: r at i
    for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i - 1][0] + (s[i] == 'r'); // e or d -> r
        dp[i][1] = dp[i - 1][1] + (s[i] == 'e'); // r -> e or d
        if (s[i] == 'r' && s[i - 1] == 'e') dp[i][1] = min(dp[i][1], dp[i - 2][0]); // r and e next to each other
        else if (s[i] == 'e' && s[i - 1] == 'd') dp[i][0] = min(dp[i][0], dp[i - 2][1]); // e and d next to each other
    }
    
    return min(dp[n - 1][0], dp[n - 1][1]);
}

int main() {
    string s = "reddere";
    cout << minOperations(s) << endl; // 最少操作次数
    return 0;
}