Changing 2D DP to 1D DP gives time complexity optimization too ?

Правка en2, от HereToDisappoint, 2017-02-06 00:15:12

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 ?

Теги dynamic programming, time complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский HereToDisappoint 2017-02-06 00:15:12 5 Tiny change: 'ion where dp[i][j] ' -> 'ion where dp[i][j] '
en1 Английский HereToDisappoint 2017-02-06 00:14:20 767 Initial revision (published)