time: 1h 34 m 13 s   vs   memory: 10 388 MB

Many tasks solved by dynamic programming are merciless to memory. It is often required to store O (n⋅m) values, which for large n and m becomes a real problem. In this article, I’ll talk about a relatively general way to save memory by working time.

Definitions and notation

Let there be some problem that requires an answer in the form , where k is the result, and path (k) is one of the possible ways to achieve this result. Moreover, k depends on two sets A and B with cardinalities n and m , and it can be expressed using linear recursion on m and n . For a better understanding, refer to an example of such a task; let's say the problem of finding editorial distances and prescriptions. You can ^read about it on Wikipedia , and see the visualizer here ^{[be careful with the habraeffect]} . Further, I reckon that the reader understands what is happening.
Obviously, the most optimal way to get the desired time - upward dynamics in both arguments, storing all n всеm intermediate values, and working, respectively, for O (n⋅m) time. For added convenience, we put n = max (m, n) (yes, reassign; otherwise, I will constantly get confused), then the operating time and the amount of occupied memory can be estimated as O (n ² ) .

Occasion: memory is finite!

To imagine that n may turn out to be over nine thousand, one does not need to have much imagination; just as you don’t need to be a genius to guess that the idea of ​​“spoiling yourself a few tens of gigabytes of memory” is doomed to failure in advance. But here we usually have much more time than we are happy to use. At this point, the reader should understand what the upward dynamics is and what they eat with it, just as well as realize what linear recursion is. Although lazy people have another option: take my word for it :) Obviously, to calculate the next value of a function, you need only a constant (most often equal to two) number of rows, and this is a clear hint that O (n) can be usedmemory. But at the same time, if we store only a fixed number of rows, then sooner or later we will be forced to “forget” the old data in order to calculate new ones. And since the output will also need this old data, you will need to read it again. It turns out a simple algorithm:

1. Set iPos = jPos = n ;
2. We calculate the values ​​of the function from (0,0) to (iPos, jPos) , each time you switch to a new line , delete the oldest one (thus, the number of lines will be constant, we denote it by k );
3. When we get to (iPos, jPos), remember the steps that are required to get from ( iPos - k , k ' ) to (iPos, jPos) , where k' is the point to which the path leads from an already forgotten line
4. Set iPos = iPos - k , jPos = k ' ;
5. If iPos and jPos are not zeros (or less), go back to step 2
6. Value and path found

You can see this algorithm in action using the example of the search for editorial distances and prescriptions using the link given above.
It is easy to see that the algorithm works for O (n ³ ) , but it consumes all O (n) memory.

Possible options

Surely many wondered: “Is it possible to do something in between?” Yes you can. Let's start with O (√n⋅n) memory and O (√n⋅n ² ) time. Actually, the changes here will be insignificant: instead of storing the k last lines, we will store √n (for the picky: max (k, √n) for small n ). This will increase the consumed memory by √n times, but then, accordingly, it will reduce the time: n ³ / √n = √n⋅n ² . With a little thought, you can understand that ∀ε∈ [0,1] can solve the problem by consuming O (n ^{2 + ε} ) time and O (n ^2-ε) memory. Visualization for ε = 0.5 is available in the same visualizer.

Afterword

A working example for the task of finding editorial distances and prescriptions can be found next to the visualizer and on the mirror . Just please, no need to tell me about Java Coding Conventions, because it has nothing to do with the matter.
Good luck :)