Skip to content

What rolling the table costs

A grid DP is reduced from a full table to a single row, cutting memory from O(r x c) to O(c).

What is given up?