Luobuyu's Blog

0%

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

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.7k 阅读时长 ≈ 2 分钟
可以使用dp求解，也可以直接使用排列组合知识。

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

题目描述：

给定 $n$ ，返回长度为 $n$ ，且仅由元音字母组成并且按照字典序排列的字符串的数量。

数据范围：
$1\le n \le 50$

题解：

很容易想到使用递推，每个字符串前面只能添加字典序比自己小的字母。因此可以得到

观察递推方程，发现第 $i$ 行只与第 $i - 1$ 行有联系，而且第 $i$ 行的更新求得是后缀和。因此可以只使用一维数组更新答案，求后缀和。

排列组合解法：

最终生成的序列是 $a\cdots ae\cdots ei\cdots io\cdots ou\cdots u$ .其中每个种类的元音字符的数量可能为0.因此可以看做 $n$ 个球放到 $5$ 个盒子里，其中有的盒子可以放 $0$ 个球。可以使用挡板法解决。因此为 $C_{n + 5 - 1} ^ 4$ .

  1. 如果每个盒子至少有一个球， $n$ 个球放到 $k$ 个盒子里。

    就是经典的挡板法 $C_{n - 1}^{k - 1}$ ，也是方程 $x_1 + x_2 + \cdots +x_k = n$ 的正整数解的组数。

  2. 如果盒子可以不放球， $n$ 个球放到 $k$ 个盒子里。

    可以先借 $k$ 个球，然后转化为了 1 中的问题。就是 $C_{n + k - 1}^{k - 1}$

    也是方程 $x_1 + x_2 + \cdots + x_k = n$ 的非负整数解的组数。

可以为 $0$ 的就借球，至少为 $m$ 的就先从 $n$ 中取出 $m - 1$ 个球，转化为至少为 $1$ 。

例题：有一类自然数数位大于等于 $3$ ，从第三个数字开始，每个数字都恰好是它前面两个数字之和，直到不能继续写下去为止。该类数有多少个？

解：前两位确定一个数，只要前两位相同后面的肯定相同，所以只用考虑前两位。

前两位为 $a,b$ ，满足 $a + b \le 9$ 。不能直接用挡板，因为 $9$ 个球不用全部放进去。

引入第三个盒子，把不用放进去的数放到第三个盒子里。因此为 $C_{10}^2 = 45$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    int countVowelStrings(int n)
    {
        vector<vector<int>> dp(n + 1, vector<int>(5, 0));
        for (int i = 0; i < 5; ++i)
            dp[1][i] = 1;
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 0; j < 5; ++j)
            {
                for (int k = j; k < 5; ++k)
                {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 5; ++i)
        {
            ans += dp[n][i];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    int countVowelStrings(int n)
    {
        vector<int> dp(5, 1);
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 3; j >= 0; --j)
            {
                dp[j] += dp[j + 1];
            }
        }
        int ans = 0;
        for (int i = 0; i < 5; ++i)
        {
            ans += dp[i];
        }
        return ans;
    }
};