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 the $[n/k] * k$th row to the $n - 1%th. Then we go downwards to compute the part of the solution between the $ik$th row and the $(i+1)k$th row. 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. Keeping every $k$th row in memory takes $O([n/k]m)$ memory. Again we minimize memory usage by using $k = sqrt{n}$

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 $ik$th row and the $(i+1)k$th row. 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. Keeping every $k$th row in memory takes $O([n/k]m)$ memory. Again we minimize memory usage by using $k = sqrt{n}$

h2. Caveats