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
h2. Caveats

The above problems have better solutions using interval trees or some other clever tricks. The sqrt trick is nice, since it improves the naive solution a lot without much effort.
h2. Additional problems