DSA · INTERVIEW & OA PREP
Recursion & Dynamic Programming
DP is the topic students fear most and interviewers love most. Every DP is just recursion with memoization — define the state, the recurrence, and the base case, and the code writes itself. Get comfortable moving from brute-force recursion to memoized to bottom-up.
Key concepts
- Identify the state: what parameters fully describe a subproblem?
- Write the recurrence: how does a subproblem combine smaller ones?
- Memoize (top-down) to cache overlapping subproblems.
- Convert to bottom-up tabulation to remove recursion overhead.
Questions that get asked
- Fibonacci / climbing stairs.
- 0/1 knapsack.
- Longest common subsequence.
- Coin change (minimum coins).
- Longest increasing subsequence.
Tip
Always start by writing the plain recursion and adding a memo dict — bottom-up is an optimization, not the starting point.
Common mistake
Jumping to a DP table without defining the state clearly. Wrong state = wrong recurrence = stuck.
Quick checks
Three tap-only questions to test your recall on this topic.
Keep going
Ready to apply? Browse live internships and sharpen your resume first.