Memoization vs. Tabulation

Memoization vs. Tabulation

• Memoization (top-down): write a recursive solution and cache results to avoid recomputation
• Tabulation (bottom-up): iteratively fill a DP table from base cases up to the answer

Example (Fibonacci):

// Memoization
function fibMemo(n, memo = []){
  if (n<=1) return n
  if (memo[n]!=null) return memo[n]
  return memo[n] = fibMemo(n-1,memo) + fibMemo(n-2,memo)
}

// Tabulation
function fibTab(n){
  const dp = Array(n+1).fill(0); dp[1]=1
  for (let i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2]
  return dp[n]
}

Choose based on convenience, stack limits, and whether you need all states or just the final result.