题面
样例
思路
如题：即转化为连续一段的相同数字用（1、2、3、4）来表示的方案数。（‘7’，‘9’）有四个按键即为（1、2、3、4），其余（1、2、3）。
那么根据乘法原理答案自然是：所有段的方案数之积。
求（1、2、3）凑数字 x 的方案数
f [ i ] ：表示用3个数字凑出数字 i {i}i 的方案数。
转移方程：f [ i ] = f [ i − 1 ] + f [ i − 2 ] + f [ i − 3 ]
同理：4个数字凑也是一样计算。
代码
class Solution { public: #define ll long long ll f[100010], g[100010]; int mod = 1e9 + 7; void init() { f[1] = 1; f[2] = 2; f[3] = 4; for (int j = 4; j <= 100000; j++) { f[j] = (f[j] + f[j - 1] + f[j - 2] + f[j - 3]) % mod; } g[1] = 1; g[2] = 2; g[3] = 4; g[4] = 8; for (int j = 5; j <= 100000; j++) { g[j] = (g[j] + g[j - 1] + g[j - 2] + g[j - 3] + g[j - 4]) % mod; } } int countTexts(string a) { init(); int n = a.size(); vector<int> v1, v2; int res = 1; for (int i = 1; i < a.size(); i++) { if(a[i] != a[i - 1]) { if(a[i - 1] == '7' || a[i - 1] == '9') v2.push_back(res); else v1.push_back(res); res = 0; } res++; } if(a[n - 1] == '7' || a[n - 1] == '9') v2.push_back(res); else v1.push_back(res); int ans = 1; for (int i = 0; i < v1.size(); i++) ans = ((ll)ans * f[v1[i]]) % mod; for (int i = 0; i < v2.size(); i++) ans = ((ll)ans * g[v2[i]]) % mod; return ans; } };
class Solution { public: int countTexts(string s) { const int mod = 1e9 + 7; vector<int> a(10, 3); a[7] = a[9] = 4; long long ans = 1; for (int i = 0, j = 0; j < s.size(); i = j) { while(j < s.size() && s[i] == s[j]) ++ j; int x = s[i] - '0', cnt = j - i; vector<long long> f(cnt + 1); f[0] = 1; for (int i = 1; i <= cnt; i++) for (int j = 1; j <= a[x]; j++) if(i - j >= 0) f[i] = (f[i] + f[i - j]) % mod; ans = ans * f[cnt] % mod; } return ans % mod; } };
