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 60%!

!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image02.png 80%!

We can start from the last saved row to n to compute the solution path from the n - 1 line to [n/k] * k line. And then go lower and lower to compute the part of the solution between the ik (i+1)k. Computing part of the path between row ik and row (i+1)k takes k * m space and k * m time. Computing the whole path takes n/k * (k * m) = nm time and km space, keeping every kth row in memory takes [n/k]m. again we minimize memory by using k = sqrt n
Caveats