牛客14487题解析：动态规划解决最小字符串翻转问题（附代码详解）
一、题目解读
牛客14487题要求给定一个仅包含字符 'R' 和 'G' 的字符串，通过翻转操作（将字符 'R' 变为 'G' 或反之）使其满足：所有字符相同，且相邻字符不同。需要求出最小翻转次数。题目本质是寻找一种优化策略，在限制条件下实现状态转换的最小代价。
二、解题思路：动态规划
1. 状态定义：使用二维DP数组 dp[i][j]，其中 dp[i][0] 表示前 i 个字符全部为 'R' 的最小翻转次数，dp[i][1] 表示前 i 个字符全部为 'G' 的最小次数。
2. 边界条件：首字符需根据当前状态判断是否需要翻转（例如，若首字符为 'G' 但要求全 'R'，则翻转一次）。
3. 状态转移：
若当前字符为 'R'，前一个字符必须为 'G'（否则需翻转），因此 dp[i][0] = dp[i-1][1] + (s[i]!= 'R')；
若当前字符为 'G'，前一个字符可为 'R' 或 'G'，取两者中较小值：dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + (s[i]!= 'G')。
4. 最终结果：取末尾字符为 'R' 或 'G' 的最小值，即 min(dp[n-1][0], dp[n-1][1])。
三、解题步骤
1. 初始化：创建 dp[n][2] 数组，根据首字符状态计算初始值。
2. 循环处理每个字符：
根据当前字符与目标状态（全 'R' 或 'G'）判断是否需要翻转，更新对应 dp 值。
利用前一个状态的最优解推导当前状态。
3. 返回最终结果：比较 dp[n-1][0] 和 dp[n-1][1] 并取最小值。
四、代码与注释
#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][1] + (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;
}注释说明：
● 使用动态规划避免重复计算，通过状态转移方程优化时间复杂度。
● 边界处理确保首字符符合初始状态要求。
● 循环中利用前缀状态信息更新当前状态，保证最优性。
五、总结
本题通过动态规划将问题拆解为局部最优决策的组合，关键在于定义状态转移方程时满足题目约束（相邻字符不同）。通过明确边界条件和状态依赖关系，可高效求解最小翻转次数。该解法时间复杂度为 O(n)，空间复杂度为 O(n)，适用于中等规模字符串问题。
链接：动态规划
原创内容 转载请注明出处
