CODEWITHSUNDEEP
dynamic-programmingmemoization
Sushil Rathore
Sushil Rathore

Reputation: 13

memoization vs dynamic programming space complexity

I want to know for a problem say LCS, we can reduce space complexity for a dp solution because when we are filling the table in dp we just use either dp[i - 1][j] or dp[i][j - 1] to fill dp[i][j] as instead of having a dp table of size m X n.

We can solve this using dp[2][n] and switch states states while calculating. Can this be possible with memorization to reduce space complexity to O(n + m)?

Upvotes: 1

Views: 868

Answers (1)

Shubham Sharma
Shubham Sharma

Reputation: 839

The simple answer is NO

In bottom Up you can remove the Rows which are unnecessary just because you know those rows would not be used again.... In Memoization , Recursion calls in any order rather than a complete formal method for example: there is a call from LCS(i,j) to LCS(i-1,j) and Let this result be calculated And saved ! Now , Recursion calls LCS(k,x) (for some other case) which leads to the same subproblem LCS(i-1,j) And Now if you had removed this stored value that wont be memoizing the solution correctly...!

You cannot be certain which subproblem to memoize and not memoize. In contrast in bottom up We are certain which subproblems would not be used again(Thats why we eliminate other rows)!

Upvotes: 1

Related Questions