DP detailed explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s illustrate this problem with a table. A row reflects the addition of a new lette
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s illustrate this problem with a table. A row reflects the addition of a new letter to a set of possible letters. A column reflects the length of the string. Cells contain the number of strings with the corresponding set of letters and length.\n\nThe number of strings consisting only of the letter "a" is obviously always 1: "a", "aa", "aaa", "aaaa", etc.\n\n![image.png](https://assets.leetcode.com/users/images/73d22971-4394-472f-ab04-4b92b385b135_1724337053.151228.png)\n\nWhen filling in the first column, it is also obvious that with the addition of a new letter, the number of strings increases by 1: ["a"], ["a", "e"], ["a", "e", "i"], etc.\n\n![image.png](https://assets.leetcode.com/users/images/b0d3e6d5-91c2-458c-90fd-28c065eef980_1724337653.4160545.png)\n\nWhen we think about filling in the "e" in the second column, we would definitely add the result from the cell above, because the cell above holds the result without the current letter. \nSo, we only need to get the number of strings we get when adding the current letter.\nWe can form strings of length 2 with "e" by adding "e" to the strings of length 1: "a" and "e". The number of them is stored to the left of the current cell.\n\n![image.png](https://assets.leetcode.com/users/images/e1aeffec-a469-41d0-bb57-0988c9f41728_1724338603.494184.png)\n\n**For "i" and the 2 column:**\n"a" -> "ai"\n"e" -> "ei"\n"i" -> "ii" from the cell to the left +\n\n"aa", "ae", "ee" from the cell above:\n\n![image.png](https://assets.leetcode.com/users/images/4dce04fe-932e-45a2-beb7-8260d6430a1b_1724339227.7925887.png)\n\n****For "i" and the 3 column:****\n"aaa", "aae", "aee", "eee" from the cell above +\n\n"aa" -> "aai"\n"ae" -> "aei"\n"ee" -> "eei"\n"ai" -> "aii"\n"ei" -> "eii"\n"ii" -> "iii" from the cell to the left.\n\n![image.png](https://assets.leetcode.com/users/images/f2d20647-6610-45ce-9fdf-652ce74ae679_1724340480.0037863.png)\n\n# Approach\nIt\'s easy to notice, that we don\'t need to store the whole table. We only need the current letter value for ```length - 1``` (left cell) and the value of the previous letter for ```length``` (cell above).\nAll we need are 5 variables (actually 4, but lets keep ```a``` for clarity).\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        int a = 1, e = 2, i = 3, o = 4, u = 5;\n        for (; n > 1; --n)\n        {\n            //above cell + left cell\n            e = a + e;\n            i = e + i;\n            o = i + o;\n            u = o + u;\n        }\n        return u;\n    }\n};\n```
['Dynamic Programming', 'C++']