Why should you care?

Once recursion TLEs, DP is the interview upgrade — fib, knapsack, LCS, paths.

See it live — copy this example

Run snippets in a .NET console app, LINQPad, or https://dotnetfiddle.net. Write Big O above every solution.

int Fib(int n, Dictionary<int,int> memo) {
  if (n <= 1) return n;
  if (memo.TryGetValue(n, out var v)) return v;
  return memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo);
}

What happened?

• Memo dictionary caches Fib(n).
• Without it, the recursion tree is exponential.

Practice next

1. Compare Fib with and without memo for n=40.
2. Write bottom-up fib array.
3. Identify overlapping subproblems in coin change.
4. Add iterative O(1) space fib.
5. Draw the dependency DAG.

Remember

DP = cache subproblems. Define state + transition. Memo or tabulate.

From TLE to AC

Recursive solution times out.

Outcome: You add memo with the right key.