Understanding the top down solution to the edit distance problem

To solve the edit distance problem using a top-down dynamic programming approach, we implement the recurrence relation directly using recursion, while storing previously computed results in a memoization table.

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.

The recursive function

We define a recursive function editDistance that takes as input references to strings s1 and s2, a 2D memoization array memo, and two indices i and j denoting the prefixes in s1 and s2. The function returns the minimum number of operations required to transform s1[0...i] into s2[0...j].

The memo array has dimensions m x n and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. Any non-negative value represents the computed minimum edit distance for that state.