Understanding the top-down solution to the longest common substring problem

To solve the longest common substring problem using a top-down dynamic programming approach, we directly implement the recurrence relation using recursion and store previously computed results in a memoization table to avoid redundant work.

The top down solution

As with any top-down solution, there is a recursive function that solves subproblems and a calling function that initializes the required data structures and triggers the computation. For the longest common substring, we define a single recursive function lcs and a calling function that iterates over all positions to find the global maximum.