C++ || 3 Approaches ||Recursion || DP || Combinations
Approach 1 : Recursion\n\n\nclass Solution {\npublic:\n    void dfs(int idx, int length, int n, int &count){\n        ++length;\n        \n        if (length ==
**Approach 1 : Recursion**\n\n```\nclass Solution {\npublic:\n    void dfs(int idx, int length, int n, int &count){\n        ++length;\n        \n        if (length == n){\n           ++count;\n           return;\n        }\n        \n        for (int i = idx ; i < 5 ; i++){\n            dfs(i,length,n,count);\n        }\n    }\n    \n    int countVowelStrings(int n) {\n        int count = 0;\n        for (int i = 0 ; i < 5 ; i++)\n            dfs(i,0,n,count);\n        return count;\n    }\n};\n```\n\n**Approach 2 : Two Dimensional DP**\n\n```\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        int dp[n][5];\n        \n        // int dp[i][j] => Nummber of strings of length i+1 and ending at character j\n        \n        for (int i = 0 ; i < 5 ; i++)\n            dp[0][i] = 1;\n        \n        for (int i = 1 ; i < n ; i++){\n            dp[i][0] = dp[i-1][0];\n            dp[i][1] = dp[i-1][1] + dp[i-1][0];\n            dp[i][2] = dp[i-1][2] + dp[i-1][1] + dp[i-1][0];\n            dp[i][3] = dp[i-1][3] + dp[i-1][2] + dp[i-1][1] + dp[i-1][0];\n            dp[i][4] = dp[i-1][4] + dp[i-1][3] + dp[i-1][2] + dp[i-1][1] + dp[i-1][0];\n        }\n        \n        int sum = 0;\n        for (int i = 0 ; i < 5 ; i++)\n            sum += dp[n-1][i];\n        \n        return sum;\n    }   \n};\n```\n\n**Approach 3: Combinations**\n\n```\nclass Solution {\npublic:\n    int countVowelStrings(int n) {\n        return (n+4)*(n+3)*(n+2)*(n+1)/24;\n    }   \n};\n```
['Dynamic Programming', 'Recursion', 'C', 'Combinatorics']