Climbing Stairs
Easy About 10 min Free, no account needed
Count the ways up a staircase taking one or two steps at a time.
The brief
A staircase has n steps; each move climbs 1 or 2. Return the number of
distinct ways to reach the top (1 <= n <= 90, the answer fits a long).
The obvious approach recurses ways(n) = ways(n-1) + ways(n-2) directly, that is
2^n calls. The hidden test asks for n = 90, which a naive recursion will
never finish. You need to avoid recomputing the same subproblem over and over.
Starter code
using System;
public class Solution
{
// TODO: return the number of distinct ways to climb n steps taking 1 or 2 at a time.
public long ClimbStairs(int n)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Related katas
- Counting Bits Easy Free Popcounts for 0..n - reuse the table you are already building.
- House Robber Easy Free Maximize the loot without robbing two adjacent houses.
- Min Cost Climbing Stairs Easy Free Pay each step you land on; reach the top as cheaply as possible.
- Unique Paths Easy Free Count the robot's lattice paths across the grid.