Why is the running time of edit distance with memoization $O(mn)$?
I'm assuming $n,m$ are the lengths of the input strings. The number of sub-problems are the number of different inputs to the recursive procedure edit_distance, ignoring the memo input. You can check that s1 is always a suffix of the first input string and that s2 is always a suffix of the second input string. Since there are $n+1$ suffixes of the first input string and $m+1$ suffixes of the second input strings, the total number of sub-problems is $(n+1)(m+1) = O(nm)$.

If evaluating the body of edit_distance (minus the recursive calls) took $O(1)$, then the total running time would be $O(nm)$. However, this is actually not the case. The function make_pair and the ensuing hash take $\Theta(|s_1|+|s_2|)$, which for a majority of function calls is $\Theta(n+m)$. Therefore the running time is actually $\Theta(nm(n+m))$ rather than $\Theta(nm)$. This slowdown is avoided in the dynamic programming solution, which does run in time $O(nm)$.

($\Theta(\cdot)$ is similar to $O(\cdot)$; whereas $O(\cdot)$ is only an upper bound, $\Theta(\cdot)$ is both a lower bound and an upper bound. I need to use it here since the fact that the algorithm runs in time $O(nm(n+m))$ doesn't preclude the possibility that it actually runs in time $O(nm)$; to preclude this possibility we need a lower bound on the running time.)