[Java/Python] Top Down DP - Clean & Concise
Python 3\npython\nclass Solution:\n    def countVowelStrings(self, n: int) -> int:\n        @lru_cache(None)\n        def dp(n, i):\n            if n == 0: retu
**Python 3**\n```python\nclass Solution:\n    def countVowelStrings(self, n: int) -> int:\n        @lru_cache(None)\n        def dp(n, i):\n            if n == 0: return 1  # Found a valid answer\n            if i == 5:  return 0  # Reach to length of vowels [a, e, i, o, u]\n            ans = dp(n, i + 1)  # Skip vowels[i]\n            ans += dp(n - 1, i)  # Include vowels[i]\n            return ans\n\n        return dp(n, 0)\n```\n\n**Java**\n```java\nclass Solution {\n    public int countVowelStrings(int n) {\n        Integer[][] memo = new Integer[n + 1][5];\n        return dp(n, 0, memo);\n    }\n\n    int dp(int n, int i, Integer memo[][]) {\n        if (n == 0) return 1; // Found a valid answer\n        if (i == 5) return 0; // Reach to length of vowels [a, e, i, o, u]\n        if (memo[n][i] != null) return memo[n][i];\n        \n        int ans = dp(n, i+1, memo); // Skip vowels[i]\n        ans += dp(n-1, i, memo); // Include vowels[i]\n        \n        return memo[n][i] = ans;\n    }\n}\n```\n\n**Complexity:**\n- Time: `O(N * vowelsLen * 2)`, where `vowelsLen` is length of vowels (=5).\n- Space: `O(N* vowelsLen)`
[]