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

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

题目：

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

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

动态规划/递归

找规律。

列出简单样例，通过列出简单样例同时观察其前后是否存在关联

注意题设：限定字母出现的位置 如 e 不能出现在a前

写n=2 时 规律可能并不明显，例子较少， 当写到n=3 时 发现此时 由a开头的所有字符串 为 n=2的数量。

原因：以a开头 后续能接上任意的 a e i o u

再观察以e开头的 发现能接上 e i o u

那么关系式就出来了

[x]

加头

```java
class Solution {
    public int countVowelStrings(int n) {
        // int a=1,e=1,i=1,o=1,u=1;
        // for(int j=1;j<n;j++){
        //     a=a+e+i+o+u;
        //     e=e+i+o+u;
        //     i=i+o+u;
        //     o=o+u;
        //     u=u;
        // }
        // return a+e+i+o+u;

        int[] []   t =  new int [n][5];
        t[0][0]=1; t[0][1]=1; t[0][2]=1; t[0][3]=1; t[0][4]=1; 
    
        for(int i =1;i<n;i++){
            t[i][0]=t[i-1][0]+t[i-1][1]+t[i-1][2]+t[i-1][3]+t[i-1][4];
            t[i][1]=t[i-1][1]+t[i-1][2]+t[i-1][3]+t[i-1][4];
            t[i][2]=t[i-1][2]+t[i-1][3]+t[i-1][4];
            t[i][3]=t[i-1][3]+t[i-1][4];
            t[i][4]=t[i-1][4];
        }
        return t[n-1][0]+t[n-1][1]+t[n-1][2]+t[n-1][3]+t[n-1][4];
    }
}

加尾

与 加头 基本类似 主体思路为 长度为n 的 字符串 与 n - 1 的关系

观察得 1. 末尾以 a 结尾的 n-1 中满足条件的一定以 a 结尾

               2.  末尾以 e 结尾的 n-1 中满足条件的为 以  a e 结尾的字符串
               3.   末尾以 i 结尾的 n-1 中满足条件的为 以  a e i  结尾的字符串
               4.   末尾以 o 结尾的 n-1 中满足条件的为 以  a e i o 结尾的字符串
               5.   末尾以 u 结尾的 n-1 中满足条件的为所有的字符串

a	e	i	o	u	数量	n
1	1	1	1	1	5	1
1	2=1+1	3=1+1+1	4=1+1+1+1	5=1+1+1+1+1	15	2
1	3=1+2	6=1+2+3	10=1+2+3+4	15=1+2+3+4+5	35	3
1	5=1+4	10=1+3+6	20=1+3+6+10	35=1+3+6+10+15	70	4

递归表达式： t[i][x]= t[i-1][0]+...t[i-1][x]

解释 当结尾为 x 时 i-1 长度的 字符串 结尾为 0-x 的 都可以在末尾添加 x 来获得长度为i 并且以x结尾的字符串

class Solution {
    public int countVowelStrings(int n) {
        int[] []   t =  new int [n][5];
        t[0][0]=1; t[0][1]=1; t[0][2]=1; t[0][3]=1; t[0][4]=1; 
    
        for(int i =1;i<n;i++){
            t[i][4]=t[i-1][0]+t[i-1][1]+t[i-1][2]+t[i-1][3]+t[i-1][4];
            t[i][3]=t[i-1][0]+t[i-1][1]+t[i-1][2]+t[i-1][3];
            t[i][2]=t[i-1][0]+t[i-1][1]+t[i-1][2];
            t[i][1]=t[i-1][0]+t[i-1][1];
            t[i][0]=t[i-1][0];
        }
        return t[n-1][0]+t[n-1][1]+t[n-1][2]+t[n-1][3]+t[n-1][4];
     }
}

由于 所求的 字符串长度 已经固定，并且有强制的前后顺序， 所有当 a e i o u 数量固定时，字符串存在且唯一。

将问题转化为 a e i o u 的各个元音字符的数量

a	e	i	o	u	数量	n
1	1	1	1	1	5	1
1	2	3	4	5	15	2
1	3	6	10	15	35	3
1	5	10	20	35	70	4