socketnaut and I were looking at 1272F - Две скобочные последовательности and challenged ourselves to solve it using as little memory as possible. From my initial submission using 118 MB, I was able to get down to 19 MB using
int16_t for DP values and using single bits for the previous step markers: 66735626.
Saketh then got it down to 3.2 MB by solving the DP using BFS to remove the DP array entirely: 66740348 (according to him, the DP values are implicit in the BFS).
Finally, we came up with a new idea to both eliminate the previous step markers and store the DP values efficiently using the observation that each DP value is +1 or -1 compared to the previous value. This uses 1.4 MB: 66796767. It's actually still $$$n^3$$$ memory, but it uses only 1 bit per entry.
Can anyone do better than this? Perhaps someone can even come up with an approach using sub-$$$n^3$$$ memory.