Definition
- Climbing Stairs – count distinct sequences of 1-step and 2-step moves to reach the top of an n-step staircase.
- Recurrence –
dp[n] = dp[n-1] + dp[n-2], the Fibonacci sequence. - Base cases –
dp[0] = 1anddp[1] = 1. - Rolling – two variables give O(n) time and O(1) space.
- Equivalence –
climb(n) = fib(n+1)with standard Fibonacci indexing. - Generalisation – K step sizes give a K-term recurrence.
The National Bank of India lets a customer clear an instalment plan of n units by paying either one or two units per transaction. The operations team counts how many distinct payment sequences finish the plan to understand the flexibility of the scheme.
Understanding the Concepts
What is the climbing stairs problem?
You are climbing a staircase with n steps. Each move takes one step or two steps. Count the number of distinct sequences of moves that reach the top. This is one of the most classic DP problems and often the first DP question in an interview.
package com.bank.dsa;
public class ClimbStairs {
public static long countWays(int n) {
if (n <= 1) return 1;
long oneBelow = 1, twoBelow = 1;
for (int i = 2; i <= n; i++) {
long current = oneBelow + twoBelow;
twoBelow = oneBelow;
oneBelow = current;
}
return oneBelow;
}
public static void main(String[] args) {
for (int n = 0; n <= 10; n++) {
System.out.println("climb(" + n + ") = " + countWays(n));
}
}
}
climb(0) = 1
climb(1) = 1
climb(2) = 2
climb(3) = 3
climb(4) = 5
climb(5) = 8
climb(6) = 13
climb(7) = 21
climb(8) = 34
climb(9) = 55
climb(10) = 89
Why is the answer a Fibonacci number?
To reach step n, the final move was either a one-step from step n-1 or a two-step from step n-2. These two groups are disjoint because they end with different moves. So dp[n] = dp[n-1] + dp[n-2], which is the Fibonacci recurrence. With base cases dp[0] = 1 and dp[1] = 1, the sequence is 1, 1, 2, 3, 5, 8, ... which matches Fibonacci shifted by one position.
How does the rolling approach work?
Since each value depends only on the two preceding values, we keep two variables and iterate forward. No array is needed.
package com.bank.dsa;
public class ClimbStairsDetailed {
public static long climb(int n) {
if (n == 0) return 1; // one way to stand still
if (n == 1) return 1; // only a single one-step
long twoBelow = 1; // dp[i-2], starts as dp[0]
long oneBelow = 1; // dp[i-1], starts as dp[1]
for (int i = 2; i <= n; i++) {
long current = oneBelow + twoBelow;
twoBelow = oneBelow;
oneBelow = current;
}
return oneBelow;
}
public static void main(String[] args) {
System.out.println("climb(4) = " + climb(4)); // 5
System.out.println("climb(10) = " + climb(10)); // 89
}
}
climb(4) = 5
climb(10) = 89
How is this different from the three-step variant?
| Aspect | Steps {1, 2} | Steps {1, 2, 3} |
|---|---|---|
| Recurrence | dp[n-1] + dp[n-2] | dp[n-1] + dp[n-2] + dp[n-3] |
| Rolling vars | 2 | 3 |
| Base cases | dp[0]=1, dp[1]=1 | dp[0]=1, dp[1]=1, dp[2]=2 |
| climb(5) | 8 | 13 |
| Sequence name | Fibonacci | Tribonacci |
package com.bank.dsa;
public class CompareStaircases {
public static void main(String[] args) {
System.out.println("Two-step climb(5): " + ClimbStairs.countWays(5));
// Three-step for comparison
long a = 1, b = 1, c = 2;
for (int i = 3; i <= 5; i++) { long d = a+b+c; a=b; b=c; c=d; }
System.out.println("Three-step climb(5): " + c);
}
}
Two-step climb(5): 8
Three-step climb(5): 13
What are common mistakes?
The most common mistake is setting dp[0] = 0 instead of 1. dp[0] = 1 represents the fact that there is one way to stand at the bottom without moving. If dp[0] = 0, the two-step jump to step 2 is not counted, and the entire sequence shifts.
// WRONG: dp[0] = 0
long a = 0, b = 1;
// climb(2) = 0 + 1 = 1 (should be 2)
// CORRECT: dp[0] = 1
long a = 1, b = 1;
// climb(2) = 1 + 1 = 2 (correct: 1+1 or 2)
Another mistake is allocating an O(n) array when only two variables are needed, wasting memory for no benefit.
What are the edge cases?
When n is 0, there is one way (do nothing). When n is 1, there is one way (a single step). When n is 2, there are two ways (1+1 or 2).
package com.bank.dsa;
public class ClimbEdge {
public static void main(String[] args) {
System.out.println(ClimbStairs.countWays(0)); // 1
System.out.println(ClimbStairs.countWays(1)); // 1
System.out.println(ClimbStairs.countWays(2)); // 2
}
}
1
1
2
How does this generalise to K step sizes?
If the allowed step sizes are a set like {1, 3, 5}, the recurrence sums dp[n - step] for each allowed step. The loop processes amounts from 1 to n, and for each amount it tries all step sizes.
package com.bank.dsa;
public class GeneralClimb {
public static long countWays(int n, int[] steps) {
long[] dp = new long[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++)
for (int step : steps)
if (step <= i) dp[i] += dp[i - step];
return dp[n];
}
public static void main(String[] args) {
System.out.println("Steps {1,2}, n=5: " + countWays(5, new int[]{1, 2}));
System.out.println("Steps {1,3,5}, n=5: " + countWays(5, new int[]{1, 3, 5}));
}
}
Steps {1,2}, n=5: 8
Steps {1,3,5}, n=5: 5
When should you use this in banking?
At the National Bank of India, the product team models an instalment scheme where customers can pay one or two units per transaction. They count the distinct payment sequences to size the audit trail database and understand how many valid completion paths exist.
package com.bank.service;
public class InstalmentPathCounter {
public static long countPaths(int instalments) {
if (instalments <= 1) return 1;
long a = 1, b = 1;
for (int i = 2; i <= instalments; i++) {
long c = a + b;
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
System.out.println("Paths for 6 instalments: " + countPaths(6));
System.out.println("Paths for 12 instalments: " + countPaths(12));
}
}
Paths for 6 instalments: 13
Paths for 12 instalments: 233
What should a senior engineer know?
A senior engineer should explicitly state that climbing stairs with steps of one or two is the Fibonacci sequence. The equivalence is climb(n) = fib(n + 1) with standard indexing. Recognising this immediately shows pattern familiarity.
Generalising to K step sizes turns the problem into a permutation-count variant of coin change. If you want combinations instead of permutations (where order does not matter), the coin loop goes outer and the amount loop goes inner.
For large n, the counts grow as powers of the golden ratio (~1.618^n), so BigInteger handles overflow. Matrix exponentiation computes the answer in O(log n) time for extreme cases.
Visual Overview
Climbing Stairs: Last Move Partitions
──────────────────────────────────────
From step N-2 ── 2-step ──┐
From step N-1 ── 1-step ──┤
▼
Step N
dp[N] = dp[N-1] + dp[N-2]
For N = 4:
dp[0]=1 dp[1]=1 dp[2]=2 dp[3]=3 dp[4]=5
Ways for step 4:
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 → 5 ways
Rolling:
[1, 1] → [1, 2] → [2, 3] → [3, 5]
dp[0,1] dp[1,2] dp[2,3] dp[3,4]
Key Takeaway
Climbing Stairs is a counting problem that reduces to the Fibonacci recurrence. The key insight is that the last move onto step n was either a one-step from step n-1 or a two-step from step n-2, and those two groups of sequences are completely separate. So dp[n] = dp[n-1] + dp[n-2], with base cases dp[0] = 1 and dp[1] = 1.
Two rolling variables give O(n) time and O(1) space. This is the Fibonacci sequence shifted by one position, so climb(n) = fib(n + 1). Recognising this equivalence is what interviewers probe for.
At the National Bank of India, the product team used this to model an instalment payment scheme where customers could pay one or two units per transaction, counting the distinct payment sequences for audit trail sizing. The rolling computation ran instantly even for large instalment counts.
Generalising to arbitrary step sizes turns the problem into a permutation-count coin change. A senior engineer knows the equivalence to Fibonacci, the O(1) space rolling approach, and the generalisation to K terms.
Remember one sentence: the ways to reach step n equal dp[n-1] + dp[n-2], which is Fibonacci computed with two rolling variables in constant space.
---