Dynamic Programming
Medium
Solving a Question with DP
A systematic 5-step framework for solving any Dynamic Programming problem.
10 min read
The Framework
Solving DP problems can be daunting. Use this 5-step framework to break it down systematically.
Step 1: Define the Objective
What are we minimizing, maximizing, or counting?
- Example: "Find the minimum cost to climb stairs."
Step 2: Identify the State
What variables uniquely define our progress? Minimize the number of state variables.
- Example:
i= current stair index. - State:
dp[i]
Step 3: Recurrence Relation (Transitions)
How do we move from one state to another? This is the core equation.
- Example:
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
Step 4: Base Cases
When does the recursion stop? What are the trivial answers?
- Example:
dp[0] = cost[0],dp[1] = cost[1]
Step 5: Implementation (Memo vs Tabulation)
Decide whether to use Top-Down (Recursive + Memoization) or Bottom-Up (Iterative + Tabulation).
- Top-Down: Easier to write, good for sparse states.
- Bottom-Up: Better space efficiency (no recursion stack), potential for state optimization.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.