Space Optimization Techniques

Concepts: pyRollingArray, pyStateCompression, pyMatrixExp

DP tables can be enormous. A naive edit distance implementation on two strings of length 10,000 needs a 10,000 x 10,000 table: 100 million entries at 8 bytes each = 800MB. That fails on most systems. Space optimization is not academic. It is the difference between a solution that runs and one that OOMs. There are three levels: rolling arrays, state compression, and mathematical shortcuts. Rolling Arrays: O(mn) to O(n) For 2D DP where dp[i][j] only depends on row i-1 (and possibly the current row i), you only need to store two rows at a time: the previous row and the current row. Overwrite prev with curr at the end of each row. This reduces space from O(mn) to O(n). Edit distance, LCS, and most grid DP problems qualify. State Compression: Reducing the State Space Sometimes the DP state can