Watch 10 video solutions for Find Number of Ways to Reach the K-th Stair, a hard level problem involving Math, Dynamic Programming, Bit Manipulation. This walkthrough by NeetCode has 721,911 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a non-negative integer k. There exists a staircase with an infinite number of stairs, with the lowest stair numbered 0.
Alice has an integer jump, with an initial value of 0. She starts on stair 1 and wants to reach stair k using any number of operations. If she is on stair i, in one operation she can:
i - 1. This operation cannot be used consecutively or on stair 0.i + 2jump. And then, jump becomes jump + 1.Return the total number of ways Alice can reach stair k.
Note that it is possible that Alice reaches the stair k, and performs some operations to reach the stair k again.
Example 1:
Input: k = 0
Output: 2
Explanation:
The 2 possible ways of reaching stair 0 are:
Example 2:
Input: k = 1
Output: 4
Explanation:
The 4 possible ways of reaching stair 1 are:
Constraints:
0 <= k <= 109