Dynamic Programming Edit Distance

Complete the edit_distance formula using dynamic programming. It should be able to compute the distance between long words efficiently.

1. Create an m+1 x n+1 matrix, where m is the length of the first string (rows) and n is the length of the second string (columns). Fill the matrix with zeros.

   For example, cat and bat would result in:

   		c	a	t
   	0	0	0	0
   b	0	0	0	0
   a	0	0	0	0
   t	0	0	0	0

2. For i in rows:

   1. For j in columns:
      1. If i is 0, the cell at [i][j] should be the value of j.
      2. Otherwise, if j is 0, the cell at [i][j] should be the value of i.
      3. Otherwise, if the corresponding characters in the strings at i-1 and j-1 are the same, then the cell at [i][j] should be the same as the cell at [i-1][j-1].
      4. Otherwise, set the cell at [i][j] to 1 plus the minimum value among the cells [i][j-1], [i-1][j] and [i-1][j-1]. (This represents the minimum-cost operation among insertion, deletion, and substitution.)

   Now you should have a table with all the edit distances for all the substrings:

   		c	a	t
   	0	1	2	3
   b	1	1	2	3
   a	2	2	1	2
   t	3	3	2	1

3. Return the value in the bottom-right cell of the table for the final answer.