大家好，我是晴天学长，这题是分组+dp的做法，不是简单的纯dp，非常值得一做，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪
1）统计打字方案数
为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。
比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母 'k' 。 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。
但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。
比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。
给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。
由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：pressedKeys = "22233"
输出：8
解释：
Alice 可能发出的文字信息包括：
"aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae" 和 "ce" 。
由于总共有 8 种可能的信息，所以我们返回 8 。
示例 2：
输入：pressedKeys = "222222222222222222222222222222222222"
输出：82876089
解释：
总共有 2082876103 种 Alice 可能发出的文字信息。
由于我们需要将答案对 109 + 7 取余，所以我们返回 2082876103 % (109 + 7) = 82876089 。
提示：
1 <= pressedKeys.length <= 1e5
pressedKeys 只包含数字 '2' 到 '9' 。
2) .算法思路
- 分组爬楼梯，只不过要分清楚，除了7和9，其他的都是从i-1，i-2，i-3转移过来。
3) .算法步骤
定义一个Solution类，包含一个countTexts方法和一个pro方法。
在countTexts方法中，初始化mod为1e9+7，n为1e5+1，以及长度为n的两个数组f和g。
调用pro方法初始化f和g数组。
定义一个变量ans并初始化为1，用于记录结果。
定义一个变量cnt并初始化为0，用于记录连续相同字符的个数。
定义一个变量left并初始化为0，用于记录当前连续相同字符的起始位置。
使用for循环遍历pressedKeys字符串，循环变量为right。
在循环中，将cnt加1，表示当前有一个连续相同字符。
获取pressedKeys字符串中right位置的字符，存入变量c。
判断是否达到字符串末尾或者下一个字符不等于c，即当前连续相同字符的结束位置。
如果满足条件，根据c字符是否为’7’或’9’来选择计算f[cnt]还是g[cnt]，并更新ans为(ans * f[cnt]) % mod。
将cnt重置为0，表示当前连续相同字符的长度为0。
将left更新为right，表示下一个连续相同字符的起始位置从right开始。
循环结束后，返回ans作为结果。
在pro方法中，初始化f和g数组的前4个元素。
使用for循环从4开始，遍历数组并计算当前位置的值。
更新f[i]为(f[i-1] + f[i-2] + f[i-3]) % mod。
更新g[i]为(g[i-1] + g[i-2] + g[i-3] + g[i-4]) % mod。
循环结束后，f和g数组的初始化完成。
4）.代码示例
class Solution {
int mod = (int)1e9+7;
int n = (int)1e5+1;
int[] f = new int[n];
int[] g = new int[n];
public int countTexts(String pressedKeys) {
int ans = 1;
int cnt = 0;
int left =0;
pro();
for (int right = 0; right < pressedKeys.length(); right++) {
cnt++;
char c = pressedKeys.charAt(right);
if (right==pressedKeys.length()-1||pressedKeys.charAt(right+1)!=c) {
ans=(int)(((long)ans*(c!='7'&&c!='9'?f[cnt]:g[cnt]))%mod);
cnt=0;
left=right;
}
}
return ans;
}
public void pro() {
f[0]=g[0]=1;
f[1]=g[1]=1;
f[2]=g[2]=2;
f[3]=g[3]=4;
for (int i = 4; i <n; i++) {
f[i] = (int) (((long) f[i - 1] + f[i - 2] + f[i - 3]) % mod);
g[i] = (int) (((long) g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % mod);
}
}
}
5）.总结
- 爬梯子类dp思想。