Intro DP — Remember Subanswers

Reuse smaller answers via a table or rolling variables.

When to use this

Fibonacci counts
House robber
Coin change

C++ template

int a = 1, b = 1;
for (int i = 2; i <= n; i++) {
    int c = a + b;
    a = b; b = c;
}
return b;

Dry run

Climb stairs n=5 → 8 ways.

Pitfalls

Wrong transition
Off-by-one
Bare recursion on large n

Say this in the interview

Define dp[i], write transition, state complexity.

Problems in this topic (3)

Each opens teach-first (animated when available), then the code panel.