Skip to content
Skein

rolling array

RU: скользящий массив

A space optimization for DP that keeps only the rows the recurrence still needs (typically the current and previous one) and overwrites the rest. It shrinks a 2D table from O(m·n) to O(min(m,n)) space, but loses the full table needed to reconstruct the path.

shortcutsexpand
search
⌘K
prev piece
k
next piece
j
cycle tier
t
this menu
?