[CPP] 2-DP Approaches || Recursion with Memoization || Memoization || O(4*N) solution
Recursion With Memoization Approach\n\nclass Solution {\npublic:\n    int mod = (int)(1e9+7);\n    int solve(int i,string &s, vector<int> &dp){\n        int n =
* ### Recursion With Memoization Approach\n```\nclass Solution {\npublic:\n    int mod = (int)(1e9+7);\n    int solve(int i,string &s, vector<int> &dp){\n        int n = s.size();\n        if(i>=n) return 1;\n        if(dp[i]!=-1) return dp[i];\n        int tot = (s[i]==\'7\'||s[i]==\'9\')?4:3;\n        int take=0;\n        for(int k=0;k<tot;k++){\n            if(i+k<n and s[i+k]==s[i]) take = (take%mod + solve(i+k+1,s,dp)%mod)%mod;\n            else break;\n        }\n        \n        return dp[i] = take%mod;\n    }\n    int countTexts(string pressedKeys) {\n        vector<int> dp(pressedKeys.size()+1,-1);\n        return solve(0,pressedKeys,dp);\n    }\n};\n```\n* ### Tabulation Approach\n```\nclass Solution {\npublic:\n    int mod = (int)(1e9+7);\n    int countTexts(string s) {\n        int n = s.size();\n        vector<int> dp(s.size()+1,0);\n        dp[n]=1;\n        \n        for(int i=n-1;i>=0;i--){\n            int tot = (s[i]==\'7\'||s[i]==\'9\')?4:3;\n            int take=0;\n            for(int k=0;k<tot;k++){\n                if(i+k<n and s[i+k]==s[i]) take = (take%mod + dp[i+k+1]%mod)%mod;\n                else break;\n            }\n\n            dp[i] = take%mod;\n        }\n        \n        return dp[0];\n    }\n};\n```
[]