MemotivaLeetCode Patterns Flashcards: Dynamic Programming, Memoization, Tabulation, Patterns

How do you optimize DP space from two-dimensional to one-dimensional?

Nortren·

How do you optimize DP space from two-dimensional to one-dimensional?

0:27

When the DP transition only depends on the previous row, you can replace the two-dimensional table with two one-dimensional arrays, current and previous, reducing space from O of m times n to O of n. After filling the current row, swap current and previous. In some problems like zero-one knapsack, you can use a single array by iterating capacity in reverse to avoid overwriting values needed for the current row's computation. This works because reverse iteration ensures each item is considered only once. ---
neetcode.io