dp

✅ When to think DP?

• Count total ways
• Find minimum
• Find maximum
• “Try all possible choices”

Try all possible choices → Recursion → DP

• We use it when greedy fails

🚀 3-Step Trick

1. Define the State

Represent the problem using an index/state.

f(i) = Answer for state i

2. Find All Choices

List every possible move from that state.

Choice 1
Choice 2
...

3. Combine Results

• Count ways → +
• Minimum → min()
• Maximum → max()
• Possible? → || return true or return false

📌 Climbing Stairs

State

f(i) = Ways to reach stair i

Choices

i-1
i-2

Combine

f(i) = f(i-1) + f(i-2)

Base Cases

f(0) = 1
f(i < 0) = 0