Memoization - Space Complexity

Your space complexity (how much memory your code uses) is $O(n)$ from two sources. - First, the dp array stores up to $n+1$ entries, one for each subproblem. - Second, the recursive call stack can go $n$ levels deep before hitting the base case.

Both contribute $O(n)$ space, so overall you use $O(n)$ memory. This is the trade-off: you sacrifice space to gain speed.

In practice, $O(n)$ space is manageable for most problems. The call stack depth can be a concern for large $n$ in languages with limited stack size, but typically it's fine. But what if recursion isn't your style? There's another way.