Yeah, I had a momentary misgiving when I hit send and thought (_well, the cell is used twice_) but in practice it is still very different than what would be considered memoization. You can make it work with just two rows at a time, forgetting all the calculated values of the earlier rows. You can also do it in one row if you work backwards in each row. If anything, it's a cache with a very specific eviction policy.

I had a whole other paragraph where I nearly convinced myself it's the same here for LCS so I'm just going to stop myself here. If you look up any texts that describe LCS they don't refer to it as using memoization. Let's not confuse things.

> If you look up any texts that describe LCS they don't refer to it as using memoization.

I challenge that actually, several resources online consider it memoization (I would too): https://www.geeksforgeeks.org/longest-common-subsequence-dp-...

I had in mind a Data Structures and Algorithms text like what is used to teach comp sci courses with. But I'm not here to denigrate the credibility of Geeks for Geeks. If we're going to cite arbitrary web sites as sources, let's refer to Wikipedia's definition:

""" An optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again. """

In LCS you are not saving the result of calling a substring method for (str1, str2, i, j) or any similar recursive method. You're keeping a constant-sized association of index pairs and their accumulated score.

If we're getting technical, I would say that what LCS uses is referred to as tabulation.

It is though, it's just a matter of perspective. The recursive method would look like this:

    str1 = ...
    str2 = ...
    def lcs(i, j):
      if i <= 0 or j <= 0:
        return 0
      res = max(score(i-1, j), score(i, j-1))
      if (str1[i] == str2[j]):
        res = max(res, score(i-1, j-1) + 1)
      return res

Now if you memoize this and make it iterative, you end up with your DP solution.

Except you've reformulated LCS as a top-down function in order to be convenient for your argument. The implementation is bottom-up not top-down.

That's exactly what DP is, every DP formulation of a recursive function is bottom up vs. top down (eg. think of the steps you need to do to get from recursive Fibonacci to DP, or knapsack). LCS is not special in that regard

My point is that the naive approach to the problem doesn't even need to use recursion, nor does the final solution, even if the path towards reasoning about the complexity calls on recursion. I prefer a narrower scope in definition for memoization, but I accept that there are many who would prefer the broader definition. I think perhaps there is even a grey area around the term, and cache, and working memory, and more. Is it no longer memoising if you're using it to build an index table? Is a cache implementation of an @memoize function decorator still memoising? IDK, it's not my intention to split hairs here.

For what it's worth, I reread the 1975 paper about the linear-space version of LCS, they do not mention memoization, even though recursion is used in both the algorithm pseudocode and in the complexity analysis. The term memoisation was coined in 1968.

https://dl.acm.org/doi/10.1145/360825.360861