The Classic 1D DP
A 1D DP problem uses a single array where each cell depends on previously computed cells. Climbing Stairs is the purest example: each step's answer depends on the previous two values, just like Fibonacci.
Recurrence
dp[0] = 1 // 1 way to stay at ground
dp[1] = 1 // 1 way to reach step 1
dp[i] = dp[i-1] + dp[i-2]
// come from 1 step back OR 2 steps back
dp[1] = 1 // 1 way to reach step 1
dp[i] = dp[i-1] + dp[i-2]
// come from 1 step back OR 2 steps back
Interactive Visualization
Source Cells Computing Computed Answer
DP Array
Step 0 of 0
Computing
—
dp[i-1] + dp[i-2]
—
Value
—
Answer dp[N]
—
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — Climbing Stairs
int climbStairs(int n) { if (n <= 1) return 1; vector<int> dp(n + 1); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[n]; } // Space optimized: O(1) int climbStairsOpt(int n) { int a = 1, b = 1; for (int i = 2; i <= n; i++) { int c = a + b; a = b; b = c; } return b; }
Complexity
Time
O(N)
Single pass filling the DP array.
Space
O(N) / O(1)
Array version O(N), optimized O(1).