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

1. 题目来源

链接：

2. 题目说明

3. 题目解析

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

有一说一确实是一道好题。在此理解这个青蛙数刚好能和最近看的操作系统多线程扯上关系，来自大佬的思想，想想确实很形象。一个线程就输出一个 "croak"，可以连续输出，但是只能算作一个线程。思路如下：

• 创建一个二维 dp[MAXN][5] 数组，即处于字符串 i 位置，处于状态 c r o a k 的线程有多少个
• 遍历字符串
• 首先将字母转换为状态编号
• 如果当前状态为 0，即代表字符 'c'，也就意味着有一个新的线程启动了，也就是有一个青蛙要开始准备叫了，就需要在该位置进行自增加一
• 如果当前状态不为 0，那么很显然就是有一个线程的状态转移到了现在这个状态，那么就需要对当前状态加 1，并且需要对前一个状态进行减 1，完成状态转移，即若当前为 'o'，那么它肯定就是从 'r' 转移过来的，并不需要关心是哪个线程，只需要关心它进行了状态转移即可
• 用当前的 dp 值是一个增量，再加上上一个 dp 状态的值就完成了状态更新。在此不需要管上阶段已经蛙叫完毕的，即仅考虑前四个状态就行了
• 全过程线程状态不能小于 0，若小于 0 就返回 -1
• 当前状态 dp 求和 sum，并取 max，得到最大的线程数就能解决问题了，这个完全可以参考线程池，即线程池大小仅需要与某时刻最大的线程数相当即可
• 最后若仍有线程未执行完毕，则出错，直接返回 -1

上述这个解法建议本地单步调试，就能豁然开朗，写的确实很冗余，这个二维的方法可以通过压缩实现一维的形式。在题解区大多数都是 1 维的直接遍历解法，思想大同小异，就不多赘述了。

参见代码如下：

// 执行用时 :76 ms, 在所有 C++ 提交中击败了100.00%的用户// 内存消耗 :11.3 MB, 在所有 C++ 提交中击败了100.00%的用户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) {
           memset(dp[0], 0, sizeof(dp[0]));        int n = str.size(), ans = 0;        for (int i = 1; i <= n; ++i) {
               char c = str[i - 1];            int cur = c2i(c);            if (cur == -1) return -1;            memset(dp[i], 0, sizeof(dp[i]));            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];            ans = max(ans, sum);        }        for (int k = 0; k < 4; ++k) if (dp[n][k] != 0) return -1;        return ans;    }};

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