Understanding the bottom up solution to the edit distance problem

To solve the edit distance problem using a bottom-up dynamic programming approach, we fill a table iteratively beginning from the smallest subproblems and building towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we depend on has already been computed and stored before we need it.

The bottom up solution

When implementing the recurrence relation using a top-down algorithm, i and j are indices into s1 and s2, and the base case occurs when either index drops below 0. If i < 0, the solution is j + 1 (we need j + 1 insertions to build the remaining prefix of s2); if j < 0, the solution is i + 1 (we need i + 1 deletions to remove the remaining prefix of s1).