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:
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.
Examples
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
3154. Find Number of Ways to Reach the K-th Stair
Hard
50 Points
Math
Dynamic Programming
Bit Manipulation
Memoization
Combinatorics
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:
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.
Examples
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
Find Number of Ways to Reach the K-th Stair - Practice Coding | SlaveCode