Staircase Traversal

Tags

Staircase Traversal

Category

Recursion

Difficulty

Medium

Problem Statement

Given a staircase of height n and a maximum step size k, determine the number of distinct ways to climb from the bottom to the top. At each point, you can take 1 to k steps (inclusive).

Intuition

The number of ways to reach step n is the sum of the ways to reach each of the previous k steps, since from any of those steps we could take a single step to reach n. This forms a recurrence relation similar to a generalized Fibonacci sequence. Using memoization or dynamic programming turns the exponential recursive solution into an efficient one. A sliding window optimization further reduces the space.

Approach

Dynamic Programming approach:

  1. Create an array dp of size n + 1, where dp[i] represents the number of ways to reach step i.
  2. Set dp[0] = 1 (one way to stand at the bottom: do nothing).
  3. For each step i from 1 to n:
    • dp[i] = sum of dp[i-1], dp[i-2], ..., dp[i-k] (only for valid indices >= 0).
  4. Return dp[n].

Sliding Window optimization: Instead of summing k values each time, maintain a running sum. When moving from dp[i] to dp[i+1], add dp[i] to the sum and subtract dp[i-k] (if it exists) from the sum.

Pseudocode

// DP with sliding window - O(n) time, O(n) space
function staircaseTraversal(height, maxSteps):
    dp = [0] * (height + 1)
    dp[0] = 1
    windowSum = 0

    for i from 0 to height:
        startOfWindow = i - maxSteps
        if startOfWindow >= 0:
            windowSum -= dp[startOfWindow]
        windowSum += dp[i - 1] if i >= 1 else 0
        // Wait, let's be clearer:

    // Clearer version:
    dp[0] = 1
    currentSum = 0
    for i from 1 to height:
        // Add the new element entering the window
        currentSum += dp[i - 1]
        // Remove the element leaving the window
        if i > maxSteps:
            currentSum -= dp[i - maxSteps - 1]
        dp[i] = currentSum
    return dp[height]

Time & Space Complexity

  • Naive recursion: O(k^n) time, O(n) space (call stack).
  • Memoized recursion / DP: O(n * k) time, O(n) space.
  • Sliding window DP: O(n) time, O(n) space.

Key Insights

  • The recurrence dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k] generalizes the Fibonacci sequence (where k = 2).
  • The sliding window optimization avoids re-summing the same values, reducing per-step work from O(k) to O(1).
  • This is equivalent to counting the number of compositions of n with parts at most k.

Edge Cases

  • Height 0: there is 1 way (do nothing), return 1.
  • Height 1: there is exactly 1 way (take 1 step), return 1.
  • Max steps >= height: the answer includes all compositions of the height, which equals 2^(n-1).
  • Max steps = 1: only one way (take 1 step at a time), return 1.
  • Large height values: the result can grow very fast; may require big integer support.

Linked mentions