Let's see how can we use less memory.
We solve the problem once and save every kth row from the best matrix and from the parent matrix.
!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image02.png 90%!

We can start from the last saved row to compute the solution path from row $[n/k] * k$ to row $n - 1$. Then we go downwards to compute the part of the solution between the row $ik$d the row $(i+1)k$ . Computing part of the path between row $ik$ and row $(i+1)k$ takes $O(km)$ space and $O(km)$ time. Computing the whole path takes $O(n/k (km)) = O(nm)$ time and $O(km)$ space. Saving the first pass rows takes $O([n/k]m)$ memory. Again, we minimize total memory usage by using $k = sqrt(n)$. This solution takes $O(sqrt(n)m)$ memory.

We can start from the last saved row to compute the solution path from row $[n/k] * k$ to row $n - 1$. Then we go downwards to compute the part of the solution between the row $ik$ and the row $(i+1)k$ . Computing part of the path between row $ik$ and row $(i+1)k$ takes $O(km)$ space and $O(km)$ time. Computing the whole path takes $O(n/k (km)) = O(nm)$ time and $O(km)$ space. Saving the first pass rows takes $O([n/k]m)$ memory. Again, we minimize total memory usage by using $k = sqrt(n)$. This solution takes $O(sqrt(n)m)$ memory.

h2. Caveats