How do you optimize DP space from two-dimensional to one-dimensional?
LeetCode Patterns Flashcards: Dynamic Programming, Memoization, Tabulation, Patterns
Аудио-карточка · 0:27Nortren·
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