Intuitive C++ Solution (With explaination)
The solution uses DP but in a way that I found much more intuitive. We start the solution from the right i.e. generate suffixes and keep prepending it to either
The solution uses DP but in a way that I found much more intuitive. We start the solution from the right i.e. generate suffixes and keep prepending it to either a, e, i, o, or u.\na = number of strings that start with a\ne = number of strings that start with e\ni = number of strings that start with i\no = number of strings that start with o\nu = number of strings that start with u\n\nSo, we can simply keep appending the string that starts with:\n1. a to only string that has a at the beginning.\n2. e to string that either has a or e at the beginning.\n3. i to string that has a, e or i at the beginning.\n.... And so on\n\n```\nint countVowelStrings(int n) {\n        int a = 1, e = 1, i = 1, o = 1, u = 1;\n        for(int j=2;j<=n;j++){\n            a = a + e + i + o + u;\n            e = e + i + o + u;\n            i = i + o + u;\n            o = o + u;\n            u = u;\n        }\n        return a + e + i + o + u;\n    }\n```\nIf you got this, try https://codeforces.com/problemset/problem/166/E, it uses a similar approach.
['Dynamic Programming', 'C', 'C++']