MediumVery High Frequency30 min
DP Fundamentals
Memoization vs tabulation, overlapping subproblems, and optimal substructure.
DP = memoization of overlapping subproblems + optimal substructure. Identify state, recurrence, base case. Top-down = recursion + memo. Bottom-up = table filling.
Dynamic Programming
Operations — Step by Step
Climbing Stairs (1D DP)
O(n)O(1) space with two variables (prev1, prev2)Step-by-step1 / 4
dp[1]=1, dp[2]=2 (base cases)
One way to reach stair 1 (1 step). Two ways to reach stair 2 (1+1 or 2).
More in Dynamic Programming
1D DP — Fibonacci & Climbing Stairs
Classic linear DP patterns with state as a single value.
2D DP — Grid & Substring Problems
Unique paths, edit distance, LCS — learn to model 2D state transition tables.
0/1 Knapsack & Unbounded Knapsack
The most important DP sub-category — choose items with weight/value constraints.