Dynamic Programming
DSA · Advanced
Definition
Dynamic Programming solves problems by breaking them into overlapping subproblems and storing their answers.
DP turns exponential brute force into polynomial solutions — a top interview topic.
Diagram
Flowchart
Example: Climbing stairs
def climb(n):
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
print(climb(5))Output: 8
Complexity
Usually O(states × transitions)
Key points
- Overlapping subproblems + optimal substructure
- Top-down = memo, bottom-up = table
- Space can often be reduced
Interview questions
0/1 knapsack recurrence?
dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]]).
DP vs greedy?
Greedy picks the local best; DP considers all choices via subproblems.