Climbing Stairs & Coin Combinations
Classic 1D recurrences from scratch.
Climbing Stairs & Coin Combinations is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]Set the Base Cases
There is one way to stay at the ground and one way to reach step 1. Those base cases seed the whole table.
dp[0], dp[1] = 1, 1Fill and Read the Answer
Loop upward and the last cell holds the count. The full solution is a tiny tabulation loop.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Shrink to Two Variables
You only need the last two values, so drop the array. This O(1) space version is the contest favorite.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bSwitch to Coin Combinations
Given coin values, count ways to make amount A. Order will not matter here, so we count combinations, not sequences.
coins = [1, 2, 5]The Combinations Table
Let dp[x] be the number of ways to form x. Start with one way to make zero: the empty set of coins.
dp = [0]*(A+1)
dp[0] = 1Loop Coins on the Outside
Put the coin loop outside the amount loop. This ordering counts each combination exactly once, never permutations.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Combinations vs Permutations
Swap the loop order and you instead count ordered ways. The loop nesting alone flips the meaning of the answer.
Coin Change Minimum Variant
For the fewest coins, store a min instead of a sum. Initialize with infinity and take 1 plus the best subproblem.
dp[x] = min(dp[x], dp[x-c] + 1)One Pattern, Many Faces
Stairs and coins share a shape: each state sums or minimizes over a few previous states. Spot that and the code writes itself.
Quick Check
Counting coin combinations, which loop order avoids duplicates?
Recap: Sum the Last Moves
You can now solve stairs and coin counting with a 1D recurrence. Each answer sums a few earlier states, and loop order decides combinations versus permutations.
Frequently asked questions
Is the “Climbing Stairs & Coin Combinations” lesson free?
Yes — the full text of “Climbing Stairs & Coin Combinations” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Climbing Stairs & Coin Combinations”?
Classic 1D recurrences from scratch. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Climbing Stairs & Coin Combinations” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence