Consider the edit distance problem: you are provided with two strings A and B of size m and n respectively. We are interested in the Levenshtein distance; insertions and deletions each have a cost of 1, mismatches have a cost of 1 and matches have a cost of 0. Derive a dynamic program to compute the number of optimal alignments of X and Y (i.e. the total number of alignments between X and Y that induce an edit distance of ?). Describe why your algorithm works. Your algorithm should use O(mn) time and space

Please explain steps of algorithms, and the solution should return the number all optimal alignments.