Leetcode diary: 1641. Count Sorted Vowel Strings [DP problem]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

This problem is HARD; I am newbie to DP still.

Looking at the problem, I knew that I could use a technique that I used before: abstracting strings into ints for easier manipulation.
This is just so I don't have to loop to check where a letter is in the array(or string) index each time.
[although I JUST realize you could just check for like "a" > "e", oh well].

The next thing I realized is that technically I don't need to store all the permutations, I just need to count how many leafs in the end of the tree-like branching out there are (or you can revisualizes as how many last iteration at the end of DFS/BFS/recursion you use).

so there is the first version code:

var countVowelStrings = function(n) {
    let answers = 0;

    function recur (n, index) {
        if(n === 0) { 
            answers++; 
            return;
        }

        for (let i = index; i < 5; i++) {
            recur(n-1, i);
        }
    }

    recur(n, 0);
    return answers; 
};

This works, but this isn't really a DP solution.
So to work on a proper DP solution, I'd need to get the permutations so that there is something to remember for:

var countVowelStrings = function(n) {
    const answers = [];
    function recur (n, currentNum) {
        if(n === 0) { 
            answers.push(currentNum); 
            return;
        }

        for (let i = 5; i > 0; i--) {
            if(currentNum !== 0 && currentNum % 10 < i) { continue; }

            const value = currentNum * 10 + i;
            recur(n-1, value);
        }
    }

    recur(n, 0);
    return answers.length; 
};

This would get me the permutations, but it won't pass the submission cause the array grew too large.
However, I thought it's best to work out an actual DP solution first so:

const memo=[[0]] //[0] is necessary;
var countVowelStrings = function(n) {
    if(n === 0) return 0;
    if(memo[n]) { return memo[n].length }

    const answers = [];
    function recur (n, currentNum) {
        if(n === 0) { 
            answers.push(currentNum); 
            return;
        }

        for (let i = 5; i > 0; i--) {
            if(currentNum !== 0 && currentNum % 10 < i) { continue; }

            const value = currentNum * 10 + i;
            recur(n-1, value);
        }
    }

    recur(n, 0);
    memo[n] = answers;
    return answers.length; 
};

But dang dude, there ain't no way I'd pass submission with like a million int permutations. So I needed someway to reduce the memory load. Fortunately for me, I figured out that I don't need the whole number representation like 55555, I just needed 5! This is because it's only the single digit number that mattered, as evidently by "currentNum % 10". Therefore I only need to store the values as 5:

const memo=[[0]] //[0] is necessary;
var countVowelStrings = function(n) {
    if(n==0) return 0;
    if(memo[n]) { return memo[n].length }

    n -= (memo.length-1);
    let currentArray; 
    while (n--) {
        const newArray = [];
        currentArray = memo[memo.length-1];
        currentArray.forEach(function(currentNum){            
            for (let i=5; i>0; i--) {
                if(currentNum !== 0 && currentNum < i) { continue; }
                newArray.push(i);
            };
        });

        memo.push(newArray);
    }

    return memo[memo.length-1].length; 
};

At this point I realized it's hard to understand the problem via recursion. Since we are already storing the whole array of previous calculations, I just needed to recall whichever the latest calculation is, this is the essence of DP! So I am back to my favorite while loop pattern and iterate on each element instead. Technically I could continue with a recursion, but it just is not intuitive enough and my head was spinning already.

This passed with really good performance, asides from some weird solutions like this.

This is also probably the best DP solution without using math or notice some weird patterns (Although honestly worthwhile to bang your brains out for). The drawback is that I use a lot more space than other solutions, but mine is also way faster than other minimal-space-no-math solutions (mine is 2 - 3X fastest and others are 4-7X).

I'll take this small victory today.

Let me know anything on your mind after reading through this, THANKS!