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.

Problem Link : SAMER08D I wrote a recursive solution and also memoized it for the problem which is a modified version of the classical LCS. I tried a lot of test cases from SPOJ Toolkit and also the sample test cases and my program gave the correct output. Not sure why my solution gives TLE. Can anyone help me out figure out the mistake?

#include <bits/stdc++.h>
using namespace std;

string a, b;
int cache[1010][1010];
int k;

int dpSol(int i, int j)
{
    if(i == a.size() || j == b.size())
        return 0;
    if(cache[i][j] != -1)
        return cache[i][j];
    int ans = 0;
    for(int l = k; ; l++)
    {
        if(i + l - 1 < a.size() && j + l - 1 < b.size())
        {
            if(a.substr(i, l) == b.substr(j, l))
                ans = max(dpSol(i + l, j + l) + l, ans);
            else
                ans = max({dpSol(i + 1, j), dpSol(i, j + 1), ans});
        }
        else
            break;
    }
    return cache[i][j] = ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> k && k)
    {
        cin >> a;
        cin >> b;
        memset(cache, -1, sizeof(cache));
        cout << dpSol(0, 0) << endl;
    }

    return 0;
}