当前位置:首页 > 牛客 > 牛客14487题解析:动态规划解决最小字符串翻转问题(附代码详解)

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

2个月前 (06-25)

牛客14487题解析:动态规划解决最小字符串翻转问题(附代码详解) 动态规划 字符串翻转 最小翻转次数  第1张

一、题目解读

牛客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),适用于中等规模字符串问题。


链接:动态规划

原创内容 转载请注明出处

分享给朋友:

相关文章

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

一、题目解读    “生命之树”是一道经典的树形结构问题,要求计算一棵带权树中,以某个节点为根的最大子树权值和。题目输入为n个节点及边信息,每个节点有权值wi,...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。