Python 3 Dynamic Programming Explained
\nclass Solution:\n    def countVowelStrings(self, n: int) -> int:\n        """\n        Given a parameter n and assuming 5 vowels, this program\n        uses d
```\nclass Solution:\n    def countVowelStrings(self, n: int) -> int:\n        """\n        Given a parameter n and assuming 5 vowels, this program\n        uses dynamic programming to determine the number of\n        possible sorted vowel strings of length n.\n        \n        The theory behind the dynamic programming is based on:\n        at length k, the number of times a vowel can be prefixed\n        to a sorted vowel string of length k - 1. For example,\n        to create the sorted vowel strings of length 2, we start\n        with the sorted strings of length 1, which are:\n        \n            \'a\', \'e\', \'i\', \'o\', \'u\'\n        \n        To create the sorted strings of length 2, the vowels\n        are prefixed to the strings of length 1 as follows:\n        \n            \'u\':    \'uu\'\n            \'o\':    \'ou\', \'oo\'\n            \'i\':    \'iu\', \'io\', \'ii\'\n            \'e\':    \'eu\', \'eo\', \'ei\', \'ee\'\n            \'a\':    \'au\', \'ao\', \'ai\', \'ae\', \'aa\'\n        \n        The dynamic programming has a column for each vowel in\n        reverse order and a row for each length starting with 1.\n        The dp can be optimized by overwriting the same row for\n        length k - 1 to create the dp for length k. For example,\n        the dp for lengths 1 and 2 will look like:\n        \n            \'u\' \'o\' \'i\' \'e\' \'a\'\n        1     1   2   3   4   5\n        2     1   3   6  10  15\n\n        :param n: length of vowel string\n        :type n: int\n        :return: number of possible sorted vowel strings of\n                 length n\n        :rtype: int\n        """\n        dp = [1] * 5\n        for k in range(n):\n            for m in range(1, 5):\n                dp[m] += dp[m - 1]\n        return dp[-1]\n\n```
['Dynamic Programming', 'Python3']