C++| DP-Beats100% - 0ms Solution | PrefixSum
IDEA:- \nInitialise dp of size 5(u,o,i,e,a) with value 1.\n\nLogic:\nFor n = 1\nStrings possible "a","e","i","o","u".\n\nNow in case of n = 2 (i.e string length
IDEA:- \nInitialise dp of size 5(u,o,i,e,a) with value 1.\n```\nLogic:\nFor n = 1\nStrings possible "a","e","i","o","u".\n\nNow in case of n = 2 (i.e string length == 2);\nFor "a" we have 5 choices to make it in sorted order i.e "a","e","i","o","u".\nFor "e", similarly we have 4 choices "e","i","o","u".\nSimilarly for "i" 3 choices, "o" 2 choices, "u" 1 choice.\nAdding up to 15 // that is where prefix sum logic comes from.\n\nFor n==3,\nfor "a", we have all 15 choices i.e including all previous choices of n=2;\nfor "e", we have total choices from "e"."i","o","u" = 10 (which is 15 - choice of "a" in n=2)\nSimilarly for all cases :)\n```\nInitially\n```\nu  o  i  e  a\n1  1  1  1  1\n```\nNow for n = 1\n```\nu  o  i  e  a\n1  2  3  4  5\nReturn dp[lastIndex];\n```\nNow for n = 2;\n```\nu  o  i  e  a\n1  3  6  10 15\nreturn dp[lastIndex];\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];\n            }\n        }\n        return dp[4];\n    }\n};\n```
['Dynamic Programming', 'C', 'Prefix Sum']