> Each step is O(n) instead of recomputing everything, and total work across all steps drops to O(n^2)

In terms of computation isn't each step O(1) in the cached case, with the entire thing being O(n)? As opposed to the previous O(n) and O(n^2).