C++ Backtracking vs Dynamic Programming beats 100.0%
First I tried backtracking and find a solution but runtime is ~1200 ms and beats 5.0% only:\n\n\nclass Solution {\npublic:\n    vector<char> vowels = {\'a\', \'
First I tried backtracking and find a solution but runtime is ~1200 ms and beats 5.0% only:\n\n```\nclass Solution {\npublic:\n    vector<char> vowels = {\'a\', \'e\', \'i\', \'o\', \'u\'};\n    int countVowelStrings(int n) {\n        int count = 0;\n        countVowelStringsHelper(n, \' \', count);\n        return count;\n    }\n    void countVowelStringsHelper(int n, char last, int &count){\n        if(n == 0){\n            count++;\n        }\n        else{\n            for(auto e: vowels){\n                if(last <= e){\n                    countVowelStringsHelper(n-1, e, count);\n                }\n            }\n        }\n    }\n};\n```\nDP Solution:\n```\nn=1, dp = {1,2,3,4,5}      return 5\nn=2, dp = {1,3,6,10,15}    return 15\nn=3, dp = {1,4,10,20,35}   return 35\n```\n\n```\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        vector<int> dp(5, 1);\n        for(int i=0; i<n; i++){\n            for(int j=1; j<5; j++){\n                dp[j] = dp[j-1] + dp[j];\n            }\n        }\n        return dp[4];\n    }\n};\n```
['Dynamic Programming', 'Backtracking', 'C', 'C++']