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

链接：1641.统计字典序元音字符串的数目
难度：Medium
标签：数学、动态规划、组合数学
简介：给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。

题解 1 - cpp

• 编辑时间：2023-03-29
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示i个字符长度时j字符为首有几种。

class Solution {
public:
    int countVowelStrings(int n) {
        int dp[55][5] = {0};
        for (int j = 0; j < 5; j++) dp[1][j] = 1;
        for (int i = 2; i <= n; i++) {
            int v = 0;
            for (int j = 0; j < 5; j++) {
                v += dp[i - 1][j];
                dp[i][j] = v;
            }
        }
        return accumulate(dp[n], dp[n] + 5, 0);
    }
};

题解 2 - python

• 编辑时间：2023-03-29
• 执行用时：20ms
• 内存消耗：14.8MB
• 编程语言：python
• 解法介绍：同上。

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

题解 3 - rust

• 编辑时间：2023-03-29
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn count_vowel_strings(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![vec![0; 5]; 55];
        for j in 0..5 {
            dp[1][j] = 1;
        }
        for i in 2..=n {
            let mut v = 0;
            for j in 0..5 {
                v += dp[i - 1][j];
                dp[i][j] = v
            }
        }
        dp[n].iter().sum()
    }
}