problem:2266. 统计打字方案数

思路：请把他看做是爬楼梯的题，这里我们可以把数字1234568看做是有三种走法的爬楼梯，把7,9看作是有4种方法的爬楼梯求方案数，根据乘法原理，答案即为他们的积。

Accode:
这里我是记忆化搜索的方法，大家也可以像灵神那样预处理一下所有的方案数。

class Solution {
public:
    vector<long long> cache;
    int now = 0;
    int mod = 1e9+7;
    long dfs(int i){
        if(i<0) return 0;
        if(i==0)return 1;
        if(cache[i]) return cache[i];
        long long ans = 0;
        if(now>=1 && now<=6 || now==8){
            ans += dfs(i-1)%mod+dfs(i-2)%mod+dfs(i-3)%mod;
        }
        else ans += dfs(i-1)%mod+dfs(i-2)%mod+dfs(i-3)%mod+dfs(i-4)%mod;
        return cache[i] = ans%mod;
    }
    int countTexts(string pressedKeys) {
        pressedKeys.push_back('0');
        long ans = 1;
        vector< long> cnt3,cnt4;
        int maxx3=0,maxx4=0;

        for(int i=0,j=0;i<pressedKeys.length();i++){

            if(pressedKeys[i]!=pressedKeys[j]){
                now = pressedKeys[j]-'0';
                if(now>=1 && now<=6 || now==8){
                    cnt3.push_back(i-j);
                    maxx3 = max(maxx3,i-j);
                }
                else {
                    cnt4.push_back(i-j);
                    maxx4 = max(maxx4,i-j);
                }
                j = i;
            }
        }
        now = 1;
        cache = vector<long long>(maxx3+1,0);
        dfs(maxx3);
        for(auto it:cnt3){
            ans=(ans*cache[it])%mod;
        }
        cache = vector<long long> (maxx4+1,0);
        now = 9;
        dfs(maxx4);
        for(auto it:cnt4){
            ans=(ans*cache[it])%mod;
        }
        return ans%mod;
    }
};

时间复杂度：$o(n)$