题解

难度：中等

知识点：数学逻辑 暴力求解 动态规划

方法一（暴力求解）

思路：

1.遍历所有涂色方法，找出其中最小的一种输出

2.对于一个长度为len的字符串，用变量i将其分为两部分（i的值为0到len），前一部分将其染色为红色R，只需要依次判断该部分的值（j的值为0到i）若为G就进行染色，将count++；后部分将其染色为绿色G，其需要依次判断该部分值（j的值为i到len）若为R就进行染色，将count++。

#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    int len=s.length();
    int min=51;
    for(int i=0;i<len;i++){
        int count=0;
        for(int j=0;j<i;j++){
            if(s[j]=='G') count++;
        }
        for(int j=i;j<len;j++){
            if(s[j]=='R') count++;
        }
        if(count<min) min=count;
    }
    cout<<min<<endl;
    return 0;
}

方法二

需要遍历一次数组,时间复杂度O(n),空间复杂度O(1)

思路：

依次遍历字符串中的每个字符，若该字符为R时，一种情况，将其之前的所有G变为R；第二种情况，将其变为G。

1.用g_count来记录当前位置之前出现的G的个数

2.用count来记录该位置按照两种思路来计算，其中更小的一种情况。

原理分析：

若count的值等于g_count时说明将之前的G都变为了R。

若count的值不等于g_count,说明之前情况也是将末尾值改为了G，因此该步骤修改R值为G会使得i位置之前序列成立。

#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    int len=s.length();
    int count=0;
    int g_count=0;
    for(int i=0;i<len;i++){
        if(s[i]=='G'){
            g_count++;
        }else{
            count=min(g_count,count+1);
        }
    }
    cout<<count<<endl;
    return 0;
}

方法三（动态规划）

思路：

1.采用二维数组dp[i][1],dp[i][2],将字符串的第i位染色为红色需要的最小次数记录在dp[i[[1]中，将字符串的第i位染色位绿色需要的最小次数记录在dp[i][2]中。

2.最后输出min(dp[len-1][i],dp[len-1][2])为最终的染色次数。

其中的状态转换公式如下：

当字符串i=0时：

if(s[0]=='R') {
        dp[0][1]=0;
        dp[0][2]=1;
}else {
        dp[0][1]=1;
        dp[0][2]=0;
}

若字符为R，那么dp[0][1]=0,不需要改色，dp[0][2]=1,表示将该位置由红色改为绿色。

若字符为G：那么dp[0][1]=1,表示将该位置颜色由绿色改为红色，dp[0][2]=0,表示不需要改色。

当i不为0时：

if(s[i]=='R'){
    dp[i][1]=dp[i-1][1];
    dp[i][2]=min(dp[i-1][1],dp[i-1][2])+1;
}else{
    dp[i][1]=dp[i-1][1]+1;
    dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
}

若当前位置为R，
dp[i][1]：该位置不改变颜色，上一步的结尾颜色只能为红色R，因此修改次数直接为dp[i-1][1]；dp[i][2]：该位置修改为绿色G，上一步结尾颜色可以为红色R也可以为绿色G。因此为min(dp[i-1][1],dp[i-1][2])+1;

若当前位置为G，
dp[i][1]：该位置修改为红色，上一步的结尾颜色只能为红色R，因此修改次数直接为dp[i-1][1]+1；
dp[i][2]：该位置不修改颜色，上一步结尾颜色可以为红色R也可以为绿色G。因此为min(dp[i-1][1],dp[i-1][2]);

例如：RGRGR

#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    int len = s.length();
    int dp[55][3];
    if(s[0]=='R') {
        dp[0][1]=0;
        dp[0][2]=1;
    }
    else {
        dp[0][1]=1;
        dp[0][2]=0;
    }

    for(int i=1;i<len;i++){
        if(s[i]=='R'){
            dp[i][1]=dp[i-1][1];
            dp[i][2]=min(dp[i-1][1],dp[i-1][2])+1;
        }else{
            dp[i][1]=dp[i-1][1]+1;
            dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
        }
    }
    cout<<min(dp[len-1][1],dp[len-1][2]);
    return 0;
}