Description

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Solution

动态规划，不妨以数组arr[5]记录可能的排列情况，其中arr[0]表示以a开头的排列，以此类推。对于长度为n+1的一个排列，假设长度n的子问题已经求解，在此基础上，arr[0]~arr[4]均可添加前缀字母a，arr[1]~arr[4]可以添加前缀字母e，以此类推......

Code

class Solution {
    int sum(int arr[], int hint) {
        int ans = 0;
        for (int i = hint; i < 5; i++) {
            ans += arr[i];
        }
        return ans;
    }
public:
    int countVowelStrings(int n) {
        int arr[5] = { 1, 1, 1, 1, 1 };
        int count = 1;
        while (count < n) {
            for (int i = 0; i < 5; i++) {
                arr[i] = sum(arr, i);
            }
            count++;
        }
        return sum(arr, 0);
    }
};