目录

一，3330. 找到初始输入字符串 I

二，3331. 修改后子树的大小

三，3332. 旅客可以得到的最多点数

四，3333. 找到初始输入字符串 II

---

一，3330. 找到初始输入字符串 I

本题就是一道找规律的题，拿示例一来说，假设Alice输入c时按的太久，那么会出现 "abbc"，"abbcc"，"abbccc"，"abbcccc" 四种可能的方案数，也就是说对于每个连续出现cnt次的字符，它们都会出现 cnt 种可能的方案，可以直接枚举，将所有cnt加起来，就是答案。

代码如下：

class Solution {public int possibleStringCount(String word) {int ans = 1;//word不变时的情况char[] ch = word.toCharArray();for(int j=1; j<ch.length; j++){if(ch[j-1] == ch[j]){ans++;}}return ans;}
}

二，3331. 修改后子树的大小

本题是一道关于树的问题，我们可以使用两次dfs，第一个dfs用来修改距离节点 x 最近的祖先节点y，唯一需要注意的点是，我们需要一个数组来记录对于每个节点，26个字母所对应的最近祖先，在不断更新这个数组时，我们需要进行回溯操作，第二个dfs就是简单的计算子树大小。

代码如下：

//双dfs
class Solution {public int[] findSubtreeSizes(int[] parent, String s) {int n = parent.length;List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList<>());for(int i=1; i<n; i++){g[parent[i]].add(i);}Arrays.fill(cnt, -1);dfs(0, g, s.toCharArray());int[] ans = new int[n];tree(0, g, ans);return ans;}int[] cnt = new int[26];void dfs(int x, List<Integer>[] g, char[] s){int tmp = cnt[s[x]-'a'];cnt[s[x]-'a'] = x;//因为会不断的添加数据，g[x]的大小会变，这里提前记录sz避免出错//当然也可以倒叙遍历，这样可以不用szint sz = g[x].size();for(int i=0; i<sz; i++){int y = g[x].get(i);if(cnt[s[y]-'a']!=-1){g[cnt[s[y]-'a']].add(y);g[x].set(i, -1);}dfs(y, g, s);}cnt[s[x]-'a'] = tmp;}void tree(int x, List<Integer>[] g, int[] ans){ans[x] = 1;for(int y : g[x]){if(y != -1){tree(y, g, ans);ans[x] += ans[y];}}}
}//单dfs
class Solution {public int[] findSubtreeSizes(int[] parent, String s) {int n = parent.length;List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList<>());for(int i=1; i<n; i++){g[parent[i]].add(i);}Arrays.fill(cnt, -1);int[] ans = new int[n];dfs(0, g, s.toCharArray(), ans);return ans;}int[] cnt = new int[26];//记录枚举到i节点时，26个字母的最近祖先节点void dfs(int x, List<Integer>[] g, char[] s, int[] ans){ans[x] = 1;int tmp = cnt[s[x]-'a'];cnt[s[x]-'a'] = x;for(int y : g[x]){dfs(y, g, s, ans);int anc = cnt[s[y]-'a'];ans[anc==-1?x:anc] += ans[y];//判断y节点是否有祖先节点t，使得s[y]==s[t]// if(anc != -1) ans[x] += ans[y];没有// else ans[anc] += ans[y];有}cnt[s[x]-'a'] = tmp;}
}

三，3332. 旅客可以得到的最多点数

本题假设第 0 天在第 1 座城市，那么接下来有两种情况：

• 留在当前城市，问题变成第 1 天到第 k - 1 天，以第 0 座城市为起点时，可以获得的最多点数
• 前往另一座城市 x，问题变成第 1 天到第 k - 1 天，以第 x 座城市为起点时，可以获得的最多点数

这样就不断形成子问题，所以我们可以使用dfs记忆化的方法来做本题，定义dfs(i，j)：从 i~k-1 天，以第 j 座城市为起点时，可以获得的最多点数。分类讨论：

• 留在当前城市，问题变成第 i+1 天到第 k - 1 天，以第 j 座城市为起点时，可以获得的最多点数，即 dfs(i，j) = dfs(i+1，j) + stayScore[i][j]
• 前往另一座城市 x，问题变成第 i+1 天到第 k - 1 天，以第 x 座城市为起点时，可以获得的最多点数，即 dfs(i，j) = dfs(i+1，x) + stayScore[j][x]

代码如下：

class Solution {public int maxScore(int n, int k, int[][] s, int[][] t) {int ans = 0;memo = new int[k][n];for(int i=0; i<n; i++){ans = Math.max(ans, dfs(0, i, k, s, t));}return ans;}int[][] memo;int dfs(int i, int j, int k, int[][] s, int[][] t){if(i == k) return 0;if(memo[i][j] > 0) return memo[i][j];int res = dfs(i+1, j, k, s, t) + s[i][j];for(int d=0; d<t.length; d++){res = Math.max(res, dfs(i+1, d, k, s, t) + t[j][d]);}return memo[i][j] = res;}
}

递推写法

class Solution {public int maxScore(int n, int k, int[][] s, int[][] t) {int ans = 0;int[][] f = new int[k+1][n];for(int i=k-1; i>=0; i--){for(int j=0; j<n; j++){f[i][j] = f[i+1][j] + s[i][j];for(int d=0; d<n; d++){f[i][j] = Math.max(f[i][j], f[i+1][d] + t[j][d]);}}}for(int x : f[0]){ans = Math.max(ans, x);}return ans;}
}

四，3333. 找到初始输入字符串 II

本题是T1的升级版，这里Alice打入的任何一个连续且相同的字符都有可能是她的失误造成的，如果我们使用dfs枚举每一个连续字符可能出现的次数，且保证初始输入>= k，那么我们至少需要O(n*(n-k))的时间复杂度，这肯定会超时。

题目要求初始输入>= k的所有可能，那么我们可以正难则反，通过计算初始输入< k 可能出现的次数，然后使用总数 - （初始输入<k）= （初始输入>=k），总数非常好计算，统计每一段连续且相同的字符数量，将它们全都乘起来，就得到总数。

接下来使用dfs计算出初始输入< k 可能出现的次数，代码如下：

class Solution {private static final int MOD = 1_000_000_007;public int possibleStringCount(String word, int k) {char[] s = word.toCharArray();int cnt = 0;long total = 1;List<Integer> lst = new ArrayList<>();for(int i=0; i<s.length; i++){cnt++;if(i == s.length-1 || s[i] != s[i+1]){lst.add(cnt);total = total * cnt % MOD;cnt = 0;}}if(lst.size() >= k) return (int)total;memo = new long[lst.size()][k+1];long res = dfs(0, k, lst);return (int)(total - res + MOD)%MOD;}long[][] memo;//O(n*k)long dfs(int i, int k, List<Integer> g){if(k <= 0) return 0;//如果k<0，说明保留了至少k个字母，返回0if(i == g.size()) return 1;if(memo[i][k] > 0) return memo[i][k];long res = 0;for(int j=1; j<=g.get(i); j++){//保留j个相同字母res = (res + dfs(i+1, k-j, g))%MOD;}return res;}
}

这里运行时会发现会超时，因为dfs的时间复杂度为O(nk)，还是太大了，是否还有其他优化的空间呢？在dfs中看不出来，所以我们把他写成递推再看看，代码如下：

class Solution {private static final int MOD = 1_000_000_007;public int possibleStringCount(String word, int k) {char[] s = word.toCharArray();int cnt = 0;long total = 1;List<Integer> lst = new ArrayList<>();for(int i=0; i<s.length; i++){cnt++;if(i == s.length-1 || s[i] != s[i+1]){lst.add(cnt);total = total * cnt % MOD;cnt = 0;}}if(lst.size() >= k) return (int)total;int n = lst.size();long[][] f = new long[n+1][k+1];Arrays.fill(f[n], 1);for(int i=0; i<n+1; i++) f[i][0] = 0;for(int i=n-1; i>=0; i--){long[] p = new long[k+1];for(int x=1; x<=k; x++){p[x] = (p[x-1] + f[i+1][x])%MOD;}for(int j=1; j<k+1; j++){f[i][j] = (p[j-1] - p[Math.max(0, j-lst.get(i)-1)])%MOD;// for(int x=1; x<=Math.min(j, lst.get(i)); x++){// 计算f[i+1][j-1]~f[i+1][j-Math.min(j, lst.get(i))]的和，使用前缀和优化//     f[i][j] = (f[i][j] + f[i+1][j-x])%MOD;// }}}return (int)((total - f[0][k])%MOD + MOD) % MOD;}
}