1641. 统计字典序元音字符串的数目-Medium.md

Description

给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例 1：

输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2：

输入：n = 2
输出：15
解释：仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后

示例 3：

输入：n = 33
输出：66045

提示：

• 1 <= n <= 50 

Solution

• 本题主要思路类似跳台阶。
• 首先，需要找到递推公式：$dp[i][j] = sum(dp[i-1][:j+1])$ 。举例解释：首先，dp[i]表示当前iteration下，index=i的元素有多少种选择（aeiou的index分别为0-4）；那么在某个iteration下：
  • $结尾为u的选择数=上一状态的所有选择数$（对于所有的选择都可以在末尾添加u），$dp[4] = dp[4]+dp[3]+dp[2]+dp[1]+dp[0]$
  • $结尾为o的选择数=上一状态的除结尾为u外的选择数$ ，（只有结尾不为u的可在结尾添o）$dp[3] = dp[3]+dp[2]+dp[1]+dp[0]$
  • 以此类推
• 此外，从上述地推公式可知，i这个维度可由省略，故简化为：$dp[j] = sum(dp[:j+1])$

炫耀一下

class Solution:
    def countVowelStrings(self, n: int) -> int:
        dp = [0]*5
        for i in range(5):
            dp[i] = 1
        for i in range(1, n):
            for j in range(4, -1, -1):
                dp[j] = sum(dp[:j+1])
        return sum(dp)