1641. Count Sorted Vowel Strings

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.

• bottom up dp

class Solution {
    int dp[51][5];
public:
    int countVowelStrings(int n) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= 4; j++) {
                for(int k = 0; k <= j; k++) {
                    dp[i][j] += dp[i-1][k];
                }
            }
        }
        return dp[n][4] + dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3];
    }
};

• top down dp

class Solution {
    int dp[50][5];
    int helper(int n, int m) {
        if(n == -1) return 1;
        if(m == -1) return 0;
        if(dp[n][m] != -1) return dp[n][m];
        dp[n][m] = 0;
        for(int i = 0; i <= m; i++)
            dp[n][m] += helper(n - 1, i);
        return dp[n][m];
    }
public:
    int countVowelStrings(int n) {
        memset(dp, -1, sizeof dp);
        return helper(n-1,4);
    }
};