传智杯省赛第三题小苯的ovo-详细版

JAY.LIN 收录于未分类

2025-03-08 约 1994 字预计阅读 4 分钟

https://bing.ee123.net/img/rand?artid=146124463

传智杯（省赛第三题）小苯的ovo （详细版）

系列文章目录

传智杯，蓝桥杯动态规划类题型解析（简易题）

文章目录

什么是动态规划？
二、核心思想：
三本题具体实现：
四、完整代码实现：

前言

这道题其实是我最想总结的一道，因为我拿到这个题，我直接想的是如何修改字符串当中的字符（就很离谱），想了解字符串内容的请见我String，StringBuffer，StringBuilder的区别那一篇，但是看到“最多”这类字眼我就知道事情不简单了，虽然DP类的题我们知道很难，包括我自己碰见动态规划的题也会傻脸，但是我们还是要知道最基础的解法，下面我们来详细的解读一下。

提示：以下是本篇文章正文内容，下面案例可供参考

题目参考：

题目输入输出样例：

一、什么是动态规划：

动态规划（Dynamic Programming，简称 DP）是一种用于求解最优化问题的方法，它通过将问题分解为子问题并逐步求解这些子问题来优化问题的解决过程。动态规划适用于那些可以通过将问题分解为重叠子问题来解决的问题。

动态规划的核心思想：

最优子结构 ：问题的最优解可以通过子问题的最优解来构建。
重叠子问题 ：子问题会被重复计算，因此通过记忆化（存储子问题的答案）来避免重复计算，从而节省时间。

动态规划的目标是通过将大问题转化为小问题的求解，最终得到最优解。

动态规划的做题步骤：

定义状态 ：将问题转化为状态表示，通常是通过一个数组或二维数组来表示问题的各个状态。
状态转移方程 ：根据问题的约束条件，推导出从一个状态到另一个状态的转移规律。
边界条件 ：确定递归的终止条件或基础情况。
优化：如果有冗余的计算，可以通过空间优化或减少状态存储的维度等手段进一步优化。

常见的模板就有：

public int dpSolution(int n) {
    int[] dp = new int[n + 1];
    
    // 初始化边界条件
    dp[0] = 0;  // 或者其他适当的值
    dp[1] = 1;  // 或者其他适当的值
    
    // 状态转移方程
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // 这是一个示例，根据具体问题的状态转移方程修改
    }
    
    return dp[n];  // 返回最终的结果
}

二、核心思想：

这道题其实真的挺有难度的在我看来，因为这道题如果暴力去写的话，求最大我们要枚举出很多很多种情况，这显然是不现实的，可能会用递归来一直重复此过程，而这道题选择动态规划显然是必要的：

最优子结构
要最大化"ovo"的数量，每个位置的选择（是否消耗修改次数形成ovo）会影响后续决策。通过将全局问题拆解为“是否在第i位结束一个ovo”的子问题，可以利用子问题的最优解组合得到全局最优解。
重叠子问题
不同位置的决策可能涉及相同的修改次数和字符检查（例如连续多个ovo可能共享部分计算），动态规划通过存储中间状态避免重复计算，提升效率。
资源分配
修改次数k是有限资源，动态规划的二维状态 dp[i][j] 能精确追踪：处理到第i个字符时，消耗j次修改能达到的最大ovo数，从而高效分配修改资源。
无后效性
一旦确定i位置的状态（如使用j次修改），后续决策仅依赖当前状态，不会影响之前的状态，符合动态规划的应用条件。

三、本题的具体实现：

首先我们肯定要定义出来状态

定义状态

定义 dp[i][j] 表示处理到字符串第 i 个字符时，使用 j 次修改后能获得的最多不相交 “ovo” 子串数量。注意i要等于3（

“ovo” 是三个连续字符组成的子串，因此至少需要处理到第3个字符才能形成第一个可能的子串。
例如字符串索引为 1-3 、 2-4 等，必须从i=3开始检查。

）

接着进行状态的更新：

将 dp[i][j] 初始化为 dp[i-1][j] ，表示不选择以 i 结尾的子串时的最优解。

for (int j = 0; j <= k; j++) {
    dp[i][j] = dp[i-1][j];
}

尝试更新状态

检查能否以 i 结尾形成一个 “ovo” 子串：

计算代价 cost ：将 i-2, i-1, i 修改为 “ovo” 所需的操作次数。
状态转移 ：若当前剩余操作次数 j ≥ cost ，则比较继承值和选择当前子串后的值，取最大。

仅当 j ≥ cost 时，允许转移

for (int j = cost; j <= k; j++) {
    dp[i][j] = Math.max(dp[i][j], dp[i-3][j-cost] + 1);
}

计算修改代价：

int cost = 0;
if (str.charAt(i-2) != 'o') cost++; // 第一个字符需是o
if (str.charAt(i-1) != 'v') cost++; // 第二个字符需是v
if (str.charAt(i) != 'o') cost++;   // 第三个字符需是o

不断更新最大值：

ans = Math.max(ans, dp[i][j]); // 记录所有可能的最大值

四、完整代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            String str = " " + sc.next(); // 转换为1-based索引

            int[][] dp = new int[n+1][k+1];
            int ans = 0;

            for (int i = 3; i <= n; i++) {
                // 继承i-1位置的状态
                for (int j = 0; j <= k; j++) {
                    dp[i][j] = dp[i-1][j];
                }

                // 计算将i-2,i-1,i三个字符变为vov的代价
                int cost = 0;
                if (str.charAt(i-2) != 'o') cost++;
                if (str.charAt(i-1) != 'v') cost++;
                if (str.charAt(i) != 'o') cost++;

                // 状态转移：消耗cost次操作，数量+1
                for (int j = cost; j <= k; j++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-3][j-cost] + 1);
                    ans = Math.max(ans, dp[i][j]);
                }
            }
            System.out.println(ans);
        }
    }
}

要点：

状态设计 ：二维数组跟踪位置和修改次数。
转移逻辑 ：分不选/选当前子串两种情况，确保不重叠。
边界处理 ：从 i=3 开始，避免越界。
复杂度 ：时间复杂度 O(nk) ，空间复杂度 O(nk)

总结

以上就是今天要讲的内容，动态规划通过状态定义和转移方程，系统地穷举所有可能，确保在修改次数限制和子串不重叠的约束下找到最优解。理解每一步的状态变化和转移条件是解题的核心。这还只是毛毛雨，我感觉理解这个过程是最重要的，希望大家都能不断学习和进步。