【动态规划入门】牛客14487题：红绿染色问题的最优解法全解析

6天前牛客题解58

题目分析

牛客网14487题"红和绿"是一道经典的动态规划问题，要求将给定的由'R'和'G'组成的字符串通过最少的修改次数变成所有'R'在前，'G'在后的形式。我们将通过详细的动态规划解法来解决这个问题。

解题思路详解

问题理解：我们需要将字符串变为所有'R'在前，'G'在后的形式，可以通过翻转字符颜色来实现。
动态规划定义：

dp[i][0]表示处理到第i个字符时，该字符为'R'的最小翻转次数
dp[i][1]表示处理到第i个字符时，该字符为'G'的最小翻转次数

状态转移：

如果当前字符选择'R'，前一个字符必须是'R'
如果当前字符选择'G'，前一个字符可以是'R'或'G'
翻转次数根据当前字符是否需要改变来增加

初始化：第一个字符的翻转次数直接计算
结果获取：最终结果是最后一位为'R'或'G'的最小值

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

int minFlips(string s) {
    int n = s.size();
    // dp[i][0]表示第i个字符为R时的最小操作次数
    // dp[i][1]表示第i个字符为G时的最小操作次数
    vector<vector<int>> dp(n, vector<int>(2, 0));
    
    // 初始化第一个字符
    dp[0][0] = (s[0] != 'R'); // 如果是G需要翻转
    dp[0][1] = (s[0] != 'G'); // 如果是R需要翻转
    
    for (int i = 1; i < n; ++i) {
        // 当前字符为R时，前一个字符只能是R
        dp[i][0] = dp[i-1][0] + (s[i] != 'R');
        // 当前字符为G时，前一个字符可以是R或G
        dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + (s[i] != 'G');
    }
    
    // 最终结果取最后一位是R或G的最小值
    return min(dp[n-1][0], dp[n-1][1]);
}

int main() {
    string s;
    cin >> s;
    cout << minFlips(s) << endl;
    return 0;
}