Space complexity to compute the optimal string alignment for the Levenshtein edit distance
There is no need for the tradeoff that Yuval suggests.  The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg.  (A linear space algorithm for computing maximal common subsequences.  Commun. ACM 18(6):341–343, 1975.)

Intuitively, Hirschberg's idea is to compute a single editing operation halfway through the optimal edit sequence, and then recursively compute the two halves of the sequence.  If we think of the optimal edit sequence as a path from one corner of the memoization table to the other, we need a modified recurrence to record where this path crosses the middle row of the table.  One recurrence that works is the following:

$$
Half(i,j) = \begin{cases}
   \infty &amp; \text{if $i&lt;m/2$}\\
   j &amp; \text{if $i=m/2$}\\
   Half(i-1,j) &amp; \text{if $i&gt;m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\
   Half(i,j-1) &amp; \text{if $i&gt;m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\
   Half(i-1,j-1) &amp; \text{otherwise}
\end{cases}
$$

The values of $Half(i,j)$ can be computed at the same time as the edit distance table $Edit(i,j)$, using $O(mn)$ time.  Since each row of the memoization table depends only on the row above it, computing both $Edit(m,n)$ and $Half(m,n)$ requires only $O(m+n)$ space.



Finally, the optimal editing sequence transforming the input strings $A[1..m]$ into $B[1..n]$ consists of the optimal sequences transforming $A[1 .. m/2]$ into $B[1 .. Half(m, n)]$ followed by the optimal sequence transforming $A[m/2 + 1 .. m]$ into $B[Half(m, n) + 1 .. n]$.  If we compute those two subsequences recursively, the overall running time obeys the following recurrence:
$$
T(m,n) = \begin{cases}
  O(n) &amp; \text{if $m\le 1$}\\
  O(m) &amp; \text{if $n\le 1$}\\
  O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right)  &amp; \text{otherwise}
\end{cases}
$$
It's not hard to prove that $T(m,n) = O(mn)$.  Similarly, since we only require space for one dynamic-programming pass at a time, the total space bound is still $O(m+n)$.  (The space for the recursion stack is negligible.)