Memoization vs tabulation

There are two ways to implement a DP. They compute the same answers; they differ in direction.

Memoization (top-down)

Write the natural recursion and add a cache. You start from the big problem and recurse down to base cases, storing each result on the way back up.

memo = {}
function solve(n):
    if base(n): return baseValue
    if n in memo: return memo[n]
    memo[n] = combine(solve(smaller(n)))
    return memo[n]

Pros: mirrors the recursion, so it's easy to derive; only computes subproblems it actually needs.
Cons: recursion overhead and call-stack depth.

Tabulation (bottom-up)

Fill a table from the base cases upward, in an order where every value you need is already computed.

dp = new array of size n+1
dp[0], dp[1] = 0, 1
for i in 2..n:
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Pros: no recursion; often easy to optimise space (e.g. keep only the last two values).
Cons: you must figure out the correct fill order, and you may compute subproblems you don't strictly need.

Which to use?

They have the same time complexity. Reach for memoization when the recursion is obvious or the subproblem space is sparse; reach for tabulation when you want to avoid deep recursion or squeeze down memory. Most problems in this section can be solved either way — pick whichever you find clearer, but be able to do both.