### DrinkWaterEatFood's blog

By DrinkWaterEatFood, history, 6 years ago,

I was recently solving a problem (ongoing contest. Will post the link after the contest ends) where I came up with a DP solution where dp[i][j] only depended on dp[][j-1]. Clearly one of the techniques to handle this type of problems is to use 1D array to compute dp[i] in an iterative manner for space optimization.

However, in the problem I was solving, even using a 2D array for dp[i][j] would not exceed memory limits. So I solved the problem using a 2D array and the verdict was Time Limit Exceeded.

But when I simply changed the 2D array to a 1D array and submitted again, the verdict was Accepted.

Why does changing a 2D array to a 1D array provide time complexity optimization too ?

 » 6 years ago, # |   0 Auto comment: topic has been updated by DrinkWaterEatFood (previous revision, new revision, compare).
 » 6 years ago, # |   0 was your 2D solution implemented using recursion ? or both of them were iterative ?
•  » » 6 years ago, # ^ |   0 Both of them were iterative. The only change in the two solutions was that i changed the 2D array (where the second component was a dummy anyway) to a 1D array.
 » 6 years ago, # |   +6 Not time complexity optimization in any way (constant factors don't count, remember?), it is more like cache optimization.
 » 6 years ago, # | ← Rev. 2 →   +11 A matrix a[n][m] is actually just an array of length n * m, and indexing it like a[x][y], it actually looks at the x*n+y-th place in the array. So the indexing is a little bit slower by itself. But this difference is really small. And the complexity is the same, it just changes the constant by a tiny margin.