#3154

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find Number of Ways to Reach the K-th Stair

Determine the total number of ways to reach the k-th stair using a state transition dynamic programming approach with combinatorial reasoning.

math dynamic programming bit manipulation memoization combinatorics

Problem Statement

You are given a non-negative integer k representing a target stair. Alice starts at stair 1 with an initial jump value of 0 and wants to reach stair k. In one operation, she can perform either of two types of jumps that adjust her current stair according to defined rules.

Return the total number of distinct sequences of operations that allow Alice to reach stair k. Each sequence can use any number of operations in any order, and you must account for all combinations while respecting the state transitions of the dynamic programming model.

Examples

Example 1

Input: k = 0

Output: 2

The 2 possible ways of reaching stair 0 are:

Example 2

Input: k = 1

Output: 4

The 4 possible ways of reaching stair 1 are:

Constraints

0 <= k <= 109

Solution Approach

Define State and Transitions

Represent each stair number as a state and define the transitions based on the two allowed operations. For each stair i, compute all reachable stairs by applying the operations, tracking counts to model the number of sequences reaching each stair.

Apply Memoization or Iterative DP

Use memoization to store results of subproblems or build a DP table iteratively. This prevents redundant computation when multiple paths lead to the same stair, directly addressing the combinatorial explosion typical in this problem pattern.

Compute Total Ways Using Combinatorics

Leverage combinatorial formulas to calculate ways to combine x operations of the second type and y operations of the first type to reach stair k. This approach optimizes beyond simple recursion while maintaining correctness with state transition tracking.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on whether you use naive recursion, memoized recursion, or iterative DP with combinatorial counting. Naive recursion can be exponential, memoization reduces it to O(k^2), and optimized combinatorial DP can approach O(k) space and time under constraints.

What Interviewers Usually Probe

Check if the candidate models state transitions correctly for both operation types.
Notice if combinatorial reasoning is applied to reduce redundant paths.
Observe how edge cases like k = 0 or negative intermediate stairs are handled.

Common Pitfalls or Variants

Common pitfalls

Failing to memoize or track states, leading to exponential recursion.
Miscounting sequences when combining two operation types in different orders.
Ignoring edge cases such as reaching stair 0 or negative indices.

Follow-up variants

Limit the number of operations allowed and count only sequences within the limit.
Include stair constraints where certain stairs cannot be stepped on.
Extend to multiple players with independent sequences interacting on the same staircase.

FAQ

What is the main pattern in Find Number of Ways to Reach the K-th Stair?

The core pattern is state transition dynamic programming combined with combinatorial counting of operation sequences.

How do you handle the case when k = 0?

Initialize the base cases correctly so that stair 0 is reachable by the defined operation sequences, avoiding off-by-one errors.

Can memoization improve performance for large k?

Yes, memoization avoids recalculating subproblems, reducing the naive exponential recursion to a manageable complexity.

Why is combinatorial reasoning useful here?

It allows counting multiple operation sequences that reach the same stair without generating all sequences explicitly.

Is iterative DP better than recursion for this problem?

Iterative DP often reduces stack overhead and, combined with combinatorial calculations, handles large k more efficiently.

terminal

Solution

Solution 1: Memoization Search

We design a function `dfs(i, j, jump)`, which represents the number of ways to reach the $k$th step when currently at the $i$th step, having performed $j$ operation 1's and `jump` operation 2's. The answer is `dfs(1, 0, 0)`.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def waysToReachStair(self, k: int) -> int:
        @cache
        def dfs(i: int, j: int, jump: int) -> int:
            if i > k + 1:
                return 0
            ans = int(i == k)
            if i > 0 and j == 0:
                ans += dfs(i - 1, 1, jump)
            ans += dfs(i + (1 << jump), 0, jump + 1)
            return ans

        return dfs(1, 0, 0)

Continue Practicing

#3539 find sum of array product of magical sequences #3116 kth smallest amount with single denomination combination #3250 find the count of monotonic pairs i