Climbing Stairs & Coin Combinations
Classic 1D recurrences from scratch.
Meet Climbing Stairs
You can take 1 or 2 steps at a time. How many ways reach step n? This classic 1D DP is just Fibonacci in disguise.
Find the Recurrence
To stand on step i you came from i-1 or i-2. So dp[i] = dp[i-1] + dp[i-2], summing both last moves.
dp[i] = dp[i-1] + dp[i-2]All lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence