Hello Codeforces community!

Problem Link : Link

I have a memoized solution for this problem. The issue here is that my complexity is : O(N^3), which leads me to TLE. All the editorials and blogs I have seen have used Bottom up approach and suffix sum to get it to O(N^2). But I'm not sure how to translate this idea to the memoized version.

int dpSol(int i, int level)
{
    if(i == n - 1)
        return 1;
    
    if(cache[i][level] != -1)
        return cache[i][level];
    
    if(arr[i] == 's')
    {
        int sum = 0;
        for(int j = 0; j <= level; ++j)
            sum = (sum + dpSol(i + 1, j)) % MOD;
        return cache[i][level] = sum;
    }
    return cache[i][level] = dpSol(i + 1, level + 1);
}

Any help will be appreciated! Thanks in advance.