本文共 1797 字，大约阅读时间需要 5 分钟。

文章目录

1. 题目来源

• 题目来源于一个经典的青蛙跳跃编程问题，题目要求计算在给定字符串中，青蛙能完成跳跃的最少线程数。

2. 题目说明

• 包含两个图片链接（图片内容为本文的核心编程问题描述），详细展示青蛙跳跃的状态转换及其编程逻辑。

3. 题目解析

• 详细分析使用递推+分析+巧妙解法解决该问题。

3.1 方法一：递推+分析+巧妙解法

• 思路：

  一个线程输出一个“croak”，可以连续输出，但只能算作一个线程。
  共同的目标：在字符串中实时跟踪青蛙的状态变化，计算最多有多少个线程同时被占用。

• 数组结构：

  使用二维数组dp[MAXN][5]，用于记录处于字符串位置i，处于 状态c r o a k的线程数量。

• 状态转换规则：

  • 当前字符为'c'，表示新线程启动，状态置为0，并自增当前状态。
  • 其他字符不为'c'，则状态转移自增当前状态并自减前一个状态。

• 更新策略：

  • 遍历字符串，每一步更新当前状态和前一个状态的数值。
  • 若出现负值，反馈错误。

3.2 解决方案

• 使用1维数组实现状态转换，减少内存占用并提升效率。
• 最终求和所有状态的总线程数，确定最大线程数。

4. 相关代码

// 以下是完整代码实现const int MAXN = 1e5 + 50;int dp[MAXN][5];int c2i(char x) {    if (x == 'c') return 0;    if (x == 'r') return 1;    if (x == 'o') return 2;    if (x == 'a') return 3;    if (x == 'k') return 4;    return -1;}class Solution {    public:        int minNumberOfFrogs(string str) {            if (str.empty()) return 0;            int n = str.size();            int ans = 0;            if (n == 0) return 0;            for (int i = 1; i <= n; ++i) {                char c = str[i - 1];                int cur = c2i(c);                if (cur == -1) return -1;                if (cur == 0) {                    dp[i][0]++;                } else {                    dp[i][cur]++;                    dp[i][cur - 1]--;                }                for (int k = 0; k < 4; ++k) {                    dp[i][k] += dp[i - 1][k];                }                for (int k = 0; k < 5; ++k) {                    if (dp[i][k] < 0) return -1;                }                int sum = 0;                for (int k = 0; k < 5; ++k) {                    sum += dp[i][k];                    if (sum > ans) ans = sum;                }            }            for (int k = 0; k < 4; ++k) {                if (dp[n][k] != 0) {                    return -1;                }            }            return ans;        }};

转载地址：http://lghpz.baihongyu.com/