1641. Count Sorted Vowel Strings

Leetcode link

解题思路

这道题规律特别明显，可以直接列出来看看：

可以看到，对于 [n = 2, a] 这个格子，它的值等于 [n = 1, a] + [n = 1, u] + [n = 1, e] + [n = 1, i] + [n = 1, o]

对于 [n = 3, u] 这个格子，它的值等于 [n = 2, u] + [n = 2, e] + [n = 2, i] + [n = 2, o]

不难看出，每一个格子的值等于其上一行同一列 到 上一行最后一列的加总

注：还有另一种规律是，从右上到左下是一个倾斜了 45 度的杨辉三角，也可以套公式来解

C++

class Solution {
public:
    int countVowelStrings(int n) {
        int a = 1, e = 1, i = 1, o = 1, u = 1;
    while(n-- > 1) {
        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;
    }
};

Javascript

var countVowelStrings = function(n) {
    let [a, e, i, o, u] = new Array(5).fill(1);
    while(n-- > 1) {
        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;
};