Definition
- Climbing Stairs – count the distinct ways to reach the top of an N-step staircase taking 1 or 2 steps.
- Recurrence –
dp[n] = dp[n-1] + dp[n-2], identical to the Fibonacci sequence. - Base cases –
dp[0] = 1(standing still) anddp[1] = 1(one step). - Rolling variables – two variables slide forward for O(n) time and O(1) space.
- Fibonacci equivalence – the answer for N steps is
fib(N+1)in the standard Fibonacci indexing. - Generalisation – allowing K step sizes gives a K-term recurrence.
The National Bank of India models a two-step customer onboarding flow where each action advances the customer by one or two steps. The product team counts the distinct action sequences that complete onboarding to understand how many valid paths exist through the process.
Understanding the Concepts
What is the climbing stairs problem?
You are climbing a staircase with N steps. Each move takes either one step or two steps. The question asks how many distinct sequences of moves reach the top. This is one of the most frequently asked dynamic programming questions in interviews.
package com.bank.dsa;
public class ClimbingStairs {
public static long countWays(int n) {
if (n <= 1) return 1;
long prev2 = 1, prev1 = 1; // dp[0] = 1, dp[1] = 1
for (int i = 2; i <= n; i++) {
long current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
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 last move was either a one-step from step N-1 or a two-step from step N-2. These two groups of sequences are completely separate because they end with different moves. So the count at step N is 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, 13, 21... This matches the Fibonacci sequence shifted by one position: climb(N) = fib(N+1).
How does the bottom-up rolling approach work?
Since each value depends only on the previous two, we keep two variables and iterate forward. This gives O(n) time and O(1) space, which is optimal.
package com.bank.dsa;
public class ClimbingStairsRolling {
public static long climb(int n) {
if (n <= 1) return 1;
long twoBelow = 1; // dp[i-2]
long oneBelow = 1; // dp[i-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));
System.out.println("climb(5) = " + climb(5));
}
}
climb(4) = 5
climb(5) = 8
How is this different from the three-step staircase?
| Aspect | Two-step (1 or 2) | Three-step (1, 2, or 3) |
|---|---|---|
| Recurrence | dp[n-1] + dp[n-2] | dp[n-1] + dp[n-2] + dp[n-3] |
| Rolling variables | 2 | 3 |
| Base cases | dp[0]=1, dp[1]=1 | dp[0]=1, dp[1]=1, dp[2]=2 |
| Sequence | Fibonacci | Tribonacci |
| climb(5) | 8 | 13 |
package com.bank.dsa;
public class TwoVsThreeStep {
public static long twoStep(int n) {
if (n <= 1) return 1;
long a = 1, b = 1;
for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
return b;
}
public static long threeStep(int n) {
if (n <= 1) return 1;
if (n == 2) return 2;
long a = 1, b = 1, c = 2;
for (int i = 3; i <= n; i++) { long d = a + b + c; a = b; b = c; c = d; }
return c;
}
public static void main(String[] args) {
System.out.println("Two-step climb(5): " + twoStep(5));
System.out.println("Three-step climb(5): " + threeStep(5));
}
}
Two-step climb(5): 8
Three-step climb(5): 13
What are common mistakes?
The most common mistake is setting dp[0] to 0 instead of 1. dp[0] = 1 represents the fact that standing at the bottom without moving is one valid way. If dp[0] = 0, the two-step move from step 0 to step 2 is not counted.
// WRONG: dp[0] = 0 means a two-step jump to step 2 is not counted
long a = 0, b = 1; // dp[0] = 0, dp[1] = 1
// climb(2) = 0 + 1 = 1 (should be 2: 1+1 or 2)
// CORRECT: dp[0] = 1 counts standing still as a valid state
long a = 1, b = 1; // dp[0] = 1, dp[1] = 1
// climb(2) = 1 + 1 = 2
What are the edge cases?
When N is zero, there is one way (do nothing). When N is one, there is one way (a single step). When N is negative, there are zero ways.
package com.bank.dsa;
public class ClimbEdgeCases {
public static void main(String[] args) {
System.out.println("climb(0) = " + ClimbingStairs.countWays(0)); // 1
System.out.println("climb(1) = " + ClimbingStairs.countWays(1)); // 1
System.out.println("climb(2) = " + ClimbingStairs.countWays(2)); // 2
}
}
climb(0) = 1
climb(1) = 1
climb(2) = 2
How does this generalise to K step sizes?
If the allowed step sizes are given as a set rather than fixed at {1, 2}, the recurrence sums over all allowed steps. This becomes the permutation-style coin-change count where order matters.
package com.bank.dsa;
public class GeneralStaircase {
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})); // 8
System.out.println("Steps {2,3}, n=6: " + countWays(6, new int[]{2, 3})); // 4
}
}
Steps {1,2}, n=5: 8
Steps {2,3}, n=6: 4
When should you use this in banking?
At the National Bank of India, Rajesh modelled a customer onboarding flow where each action advanced by one or two steps. The product team needed the count of distinct action sequences to understand flexibility and to size their audit-trail database. The rolling Fibonacci approach computed results instantly.
package com.bank.service;
public class OnboardingPathCounter {
public static long countPaths(int steps) {
if (steps <= 1) return 1;
long a = 1, b = 1;
for (int i = 2; i <= steps; i++) {
long c = a + b;
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
System.out.println("Paths for 5-step onboarding: " + countPaths(5));
System.out.println("Paths for 10-step onboarding: " + countPaths(10));
}
}
Paths for 5-step onboarding: 8
Paths for 10-step onboarding: 89
What should a senior engineer know?
A senior engineer should recognise that climbing stairs with steps of one or two is exactly the Fibonacci sequence. The insight is that the last move partitions the sequences into two non-overlapping groups, and summing them gives the recurrence.
This problem is often the gateway to more complex DP questions. Interviewers use it to check whether a candidate can identify the Fibonacci structure, optimise space to O(1), and generalise to K step sizes. Being able to state that climb(N) = fib(N+1) with the standard Fibonacci indexing shows real understanding.
Visual Overview
Climbing Stairs: Last Move Partitions
──────────────────────────────────────
To reach step N:
All sequences All sequences
ending with ending with
a 1-step a 2-step
from N-1 from N-2
│ │
└───────┬───────────┘
│
dp[N] = dp[N-1] + dp[N-2]
Example for N = 4:
From step 3 (1-step): 1+1+1+1, 1+2+1, 2+1+1 → 3 ways
From step 2 (2-step): 1+1+2, 2+2 → 2 ways
Total: 3 + 2 = 5
Sequence: 1, 1, 2, 3, [5], 8, 13, 21... (Fibonacci)
Key Takeaway
Climbing Stairs with steps of one or two is the canonical Fibonacci Numbers pattern problem. The key observation is that the last move onto any step was either a one-step or a two-step, which splits the ways into two non-overlapping groups. The count at step N is the sum of the counts at the two preceding steps, which is exactly the Fibonacci recurrence.
Bottom-up with two rolling variables gives O(n) time and O(1) space. The base cases are dp[0] = 1 (standing still counts as one way) and dp[1] = 1 (a single step). Getting dp[0] wrong is the most common mistake and shifts the entire sequence.
At the National Bank of India, Rajesh used this to model a customer onboarding flow where each action advanced by one or two steps, counting the distinct action sequences for audit and capacity planning. The rolling computation ran in constant space and returned results instantly.
The senior-level insight is that this problem is Fibonacci by another name: climb(N) equals fib(N+1) with standard indexing. Recognising that equivalence and being able to generalise to K step sizes is what interviewers probe for.
Remember one sentence: the count at step N is dp[N-1] plus dp[N-2], which is the Fibonacci sequence computed with two rolling variables in constant space.
---