Let A be an array that holds a string of length m, and let B be an array that holds a string of length n. Number the members of arrays A and B starting at 0, in the C++ convention. Define D[i][j] to be the edit distance between the length i prefix of A and the length j prefix of B. Then the following facts can be shown.
The facts about D, if used naively, might suggest a recursive algorithm. If you write this program using naive recursion, it will be ASTOUNDINGLY inefficient. The same thing will be computed over and over. Instead, store the values in a two-dimensional array, so that you can look them up. (If you think about the algorithm, you will see that the same value gets looked up more than once. Using recursion would require recomputing them. Recursion amplifies bad as well as good things, and makes the recursive approach very bad. The recursive approach can end up computing some things thousands of times.)
Test your program, and check whether the answers are correct. Turn in a printout of your program.