15303105423 发表于 2025-6-19 15:29:33

牛客14487题解析:动态规划解决最小字符串翻转问题(附代...



https://www.xinaozhilu.cn/zb_users/upload/2025/06/202506081749375438357002.jpg

一、题目解读牛客14487题要求给定一个仅包含字符 'R' 和 'G' 的字符串,通过翻转操作(将字符 'R' 变为 'G' 或反之)使其满足:所有字符相同,且相邻字符不同。需要求出最小翻转次数。题目本质是寻找一种优化策略,在限制条件下实现状态转换的最小代价。二、解题思路:动态规划1. 状态定义:使用二维DP数组 dp,其中 dp 表示前 i 个字符全部为 'R' 的最小翻转次数,dp 表示前 i 个字符全部为 'G' 的最小次数。2. 边界条件:首字符需根据当前状态判断是否需要翻转(例如,若首字符为 'G' 但要求全 'R',则翻转一次)。3. 状态转移:    若当前字符为 'R',前一个字符必须为 'G'(否则需翻转),因此 dp = dp + (s!= 'R');    若当前字符为 'G',前一个字符可为 'R' 或 'G',取两者中较小值:dp = min(dp, dp) + (s!= 'G')。4. 最终结果:取末尾字符为 'R' 或 'G' 的最小值,即 min(dp, dp)。三、解题步骤1. 初始化:创建 dp 数组,根据首字符状态计算初始值。2. 循环处理每个字符:    根据当前字符与目标状态(全 'R' 或 'G')判断是否需要翻转,更新对应 dp 值。    利用前一个状态的最优解推导当前状态。3. 返回最终结果:比较 dp 和 dp 并取最小值。四、代码与注释
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

注释说明:● 使用动态规划避免重复计算,通过状态转移方程优化时间复杂度。● 边界处理确保首字符符合初始状态要求。● 循环中利用前缀状态信息更新当前状态,保证最优性。
原文:牛客14487
页: [1]
查看完整版本: 牛客14487题解析:动态规划解决最小字符串翻转问题(附代...