Dynamic Programming
DP State Tables
Watch tabulation fill one state at a time with dependencies, current result, and per-step time and space complexity.
O(n)
State 00
State 10
State 20
State 30
State 40
State 50
State 60
State 70
State 80
Result
-
Time
O(n)
Space
O(n)
Step Note
Count ways to climb 8 stairs.
function climbStairs(n: number) {
const dp = Array(n + 1).fill(0)
dp[0] = 1
for (let i = 1; i <= n; i++) {
const twoBack = i >= 2 ? dp[i - 2] : 0
dp[i] = dp[i - 1] + twoBack
}
return dp[n]
}