Dynamic Programming - Python [100%] [Explanation + code]
In this problem, the pattern I observed was prepending \'a\' to all the strings of length n-1 does not affect any order. Similarly, \'e\' can be prepended to st
In this problem, the pattern I observed was prepending \'a\' to all the strings of length n-1 does not affect any order. Similarly, \'e\' can be prepended to strings starting with \'e\' and greater vowels and so on.\n\nSo we have our subproblem.\n\n**How do we fill the DP Table?**\nLets, take an example of n = 3\n\n![image](https://assets.leetcode.com/users/images/b9b6fce5-8a9a-4428-a969-6dc9beb4f028_1604210585.3769555.png)\n\nFor n = 1, number of strings starting with u is 1, with o is 2 (including the ones starting with u) and so on.\nFor n = 2, number of strings starting with u is 1, but for o its (number of strings of length 2 starting with u + number of strings of length 1 starting with o) and so on.\ndp[i][j] represents total no. of string of length i , starting with characters of column j and after j. (Thanks @[rkm_coder](https://leetcode.com/rkm_coder/) for the correction)\n\nThe recursive expression is : dp[i][j] = dp[i - 1][j] + dp[i][j + 1]\n\nFinally, we will get our answer at dp[n][0]\n\nThe running time of my algorithm is **O(n)**\n\n```\nclass Solution:\n    def countVowelStrings(self, n: int) -> int:\n        dp = [[i for i in range(5,0,-1)] for _ in range(n)]   # intialize dp matrix\n        \n        for i in range(1,n):\n            for j in range(3,-1,-1):\n                dp[i][j] = dp[i - 1][j] + dp[i][j + 1]   # dp expression\n                \n        return dp[n-1][0]\n```\n\nAlso check out Java implementation here: https://leetcode.com/problems/count-sorted-vowel-strings/discuss/918728/java-dp-beats-100
['Dynamic Programming', 'Python3']