Memoization is preferred over tabulation when the problem requires us to compute all possible values of a function, and we only need a subset of those values to solve the problem efficiently. This is because memoization avoids computing unnecessary values and saves space by only storing the computed values that are actually needed.
An example of such a problem is the longest increasing subsequence problem, which asks us to find the length of the longest increasing subsequence in a given sequence of integers.
Here is an example implementation of the problem using memoization:
def lis_memoization(nums):
memo = [-1] * len(nums)
def lis_helper(i):
if memo[i] != -1:
return memo[i]
result = 1
for j in range(i):
if nums[j] < nums[i]:
result = max(result, 1 + lis_helper(j))
memo[i] = result
return result
return max([lis_helper(i) for i in range(len(nums))])
In the above implementation, we use a memo list to store the computed values of the function lis_helper(i). If the value is already computed, we simply return it from the memo list, otherwise, we compute the value recursively and store it in the memo list for future use.
Here is an example implementation of the same problem using tabulation:
def lis_tabulation(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], 1 + dp[j])
return max(dp)
In the above implementation, we use a dp list to store the computed values of the function. We use nested loops to iterate through all possible subproblems, and update the dp list accordingly.
Although both implementations have the same time complexity of O(n^2), the memoization implementation has a better space complexity of O(n), as it only stores the computed values that are actually needed. In contrast, the tabulation implementation requires storing all the computed values in the dp list, even if we only need a subset of those values to solve the problem.
Therefore, in problems where we only need a subset of the computed values, memoization is always preferred over tabulation, as it saves space and avoids computing unnecessary values.