【Leetcode每日笔记】1641. 统计字典序元音字符串的数目(Python)

参考链接： Python程序来计算每个元音的数量

文章目录

 题目解题思路动态规划状态定义状态转移方程

  代码

题目 

 给你一个整数 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 

解题思路 

动态规划 

状态定义 

dp[i][j]表示第i轮以第j个元音字母作为字符串结尾的个数，例如dp[0][2]表示第0轮“i”作为字符串结尾的个数，是1； 同时可以发现，每一轮的个数，只与上一轮有关，那么就直接可以用一维数组dp[i]表示第i个字母作为字符串结尾的个数； 

状态转移方程 

[“a”,“e”,“i”,“o”,“u”]，如果想要添加“e”，可以发现只能在“a”和“e”后面添加，也就是说，dp[1][1] = dp[0][1]+dp[0][0]，同理dp[1][2] = dp[0][0]+dp[0][1]+dp[0][2]，以此类推，那么转换为一维数组可以发现dp[1] += dp[0],dp[2] += dp[1]。 得到状态转移方程dp[i] += dp[i-1] 

代码 

class Solution:

    def countVowelStrings(self, n: int) -> int:

        dp = [1,1,1,1,1]

        for _ in range(n-1):

            for i in range(1,5):

                dp[i] += dp[i-1]

        return sum(dp)