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

Many problems solved with the help of dynamic programming relate to memory mercilessly. It is often necessary to store O (n⋅m) values, which becomes a real problem for large n and m . In this article I will talk about a relatively common way to save memory at the expense of work time.

Definitions and notation

Let there be some task that requires a response in the form <k, path (k)> , where k is the result, and path (k) is one of the possible ways to achieve this result. At the same time, k depends on two sets A and B with powers n and m , and it can be expressed using linear recursion from m and n . For a better understanding it is worth referring to the example of such a task; say, the task of finding editorial distances and prescriptions. You can ^read about it on Wikipedia , and see the visualizer - here ^{[be careful with the habra effect ]} . Next, I rely on the reader to understand what is happening.
Obviously, the time-optimal way to get what you are looking for is an upward trend in both arguments, storing all n⋅m intermediate values, and working, respectively, in O (n⋅m) time. To make things easier, we put n = max (m, n) (yes, reassign; otherwise I will be constantly confused), then the operation time and the amount of memory taken can be estimated as O (n ² ) .

Occurrence: memory is finite!

To imagine that n can be more than nine thousand, you do not need to have a lot of fantasy; just as one doesn’t need to be a genius to guess that the idea of ​​“grabbing a few dozen gigabytes of memory” is doomed to failure. But now, as a rule, we have significantly more time than we are happy to use. At this point, the reader should understand what is upward dynamics, and with what it is eaten, exactly like to realize what linear recursion is. Although, lazy people have another option: take my word :) Obviously, to calculate the next value of the function, you need only a constant number (most often equal to two), and this is an obvious hint that you can use O (n) of memory. But at the same time, if we store only a fixed number of lines, then sooner or later we will have to “forget” the old data in order to calculate new ones. And since the output of these old data is also needed, you will need to read them 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, denote this by k );
3. When we get to (iPos, jPos), let's 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 the already forgotten line
4. Set iPos = iPos - k , jPos = k ' ;
5. If iPos and jPos do not turn out to be zeros (or less), go back to step 2
6. Value and path found

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

Possible options

Surely many people wondered: “Is it possible to make something average?” Yes, it is possible. Let's start with O (√n⋅n) memory and O (√n⋅n ² ) time. Actually, the changes here will be insignificant: instead of storing the last k lines, we will store √n (for the picky: max (k, √ n ) for small n ) . This will increase the memory consumption by √n times, but then and accordingly will reduce the time: n ³ / √n = √n⋅n ² . After 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 . Only please, you do not need to tell me about the Java Coding Conventions, because it has nothing to do with business.
Good luck! :)