LeetCode-1641-统计字典序元音字符串的数目

原题链接：https://leetcode-cn.com/problems/count-sorted-vowel-strings/
标签： 动态规划、排列组合

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

image.png

解题思路：

1. 动态规划
   1.1. 当n=1时，即从5个元音字母中选一个，那么以每个元音字母结尾能组成的结果都为1，即a[0][j]=1 when j from 0 to 4；
   1.2. 分析n=2的情况，当元音取i结尾时，比取e结尾时，多了一个n=1时的i，即a[i][j] = a[i-1][j] + a[i][j-1]
   1.3. 最后返回第n行的结果数组和sum(a[-1])

2. 排列组合方法：有n个数，在其中插入4个隔板，就分为了5组，再在(n+4)中取4个，即

Python3代码：

class Solution:
    def countVowelStrings(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 5
        arr = [[0 for _ in range(5)] for _ in range(n)]

        for i in range(5):
            arr[0][i] = 1

        for i in range(1, n):
            for j in range(5):
                if j == 0:
                    arr[i][j] = 1
                else:
                    arr[i][j] = arr[i-1][j] + arr[i][j-1]
        
        return sum(arr[-1])

class Solution:
    def countVowelStrings(self, n: int) -> int:
        return int((n+4)*(n+3)*(n+2)*(n+1)/4/3/2)