How do I calculate the time complexity of this memoized algorithm?
Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values:

The number of elements that will be calculated (or a bound on this number. Notice that &quot;elements that would be calculated&quot; refers to the elements you save with the memoization technique)
The time it takes to process an item, assuming you know the results of every recursive call it would have done (or a bound on this number)

In your case:

The memoization saves elements up to $n=len(s)$ (every element in the dictionary is smaller or equal to $n$ and therefore you will calculate at most $n$ values)
Processing each element takes $O(n)$ time (in the recurse function, there is a for i in range(n):)

Therefore, for every new element you calculate (there are at most $n$ such values) you will spend $O(n)$ time, and thus the algorithm will take $n\cdot O(n)=O(n^2)$ in the worst case analysis.
Notice this is not an improvement from any naive algorithm that goes through every sublist - as by combinatorical counting there are ${n\choose2}={n!\over2!\cdot(n-2)!}={n\cdot(n-1)\over2}=O(n^2)$ different sublists