Memoization: top-down recursion with a cache; evaluates only the subproblems you actually touch. Great when many states are unreachable or pruned.
Tabulation: bottom-up iteration; fills states in dependency order and avoids recursion overhead. Ideal when you know the order and most states are needed.
Both require overlapping subproblems and optimal substructure to pay off.

Tabulation vs Memoization (at a glance)

Tabulation (Bottom‑up)

State order can be trickier to derive; you must respect dependencies.
Code can become verbose when many boundary conditions are involved.
Often faster in practice: no recursion or call‑stack overhead.
Computes all states at least once; shines when most states are needed.
Table is filled systematically from small to large states.

Memoization (Top‑down)

Transition is easy to express by starting from a clear recursion.
Code is often simpler: add a cache on top of the recursive solution.
May be slower due to recursive overhead and function calls.
Skips unreachable states; computes only what the recursion touches.
Cache fills on demand; not all entries are necessarily visited.

Example: Rod Cutting

Given prices for pieces of length 1..n, find the maximum revenue for a rod of length n. Try all first cuts and combine with the best for the remaining length.

Top‑down with Memoization

O(n²) time, O(n) space

Pseudocode

1function rodCut(n, price):
2  memo = array(n+1, -INF)
3  function f(len):
4    if len == 0: return 0
5    if memo[len] != -INF: return memo[len]
6    best = 0
7    for cut in 1..len:
8      best = max(best, price[cut] + f(len - cut))
9    memo[len] = best
10    return best
11  return f(n)

Bottom‑up Tabulation

O(n²) time, O(n) space

Pseudocode

1function rodCutTab(n, price):
2  dp = array(n+1, 0)
3  for len in 1..n:
4    best = 0
5    for cut in 1..len:
6      best = max(best, price[cut] + dp[len - cut])
7    dp[len] = best
8  return dp[n]

Notes

Both variants are quadratic in the rod length due to the nested loop over the first cut.
Top‑down is convenient to write from a recurrence; bottom‑up is easy to optimize further (e.g., space or order tweaks).

DP Fundamentals

Sequences & Strings

1function rodCut(n, price): 2 memo = array(n+1, -INF) 3 function f(len): 4 if len == 0: return 0 5 if memo[len] != -INF: return memo[len] 6 best = 0 7 for cut in 1..len: 8 best = max(best, price[cut] + f(len - cut)) 9 memo[len] = best 10 return best 11 return f(n)