3154. Find Number of Ways to Reach the K-th Stair
Description
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:
- Go down to stair
i - 1
. This operation cannot be used consecutively or on stair 0. - Go up to stair
i + 2jump
. And then,jump
becomesjump + 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:
- Alice starts at stair 1.
- Using an operation of the first type, she goes down 1 stair to reach stair 0.
- Alice starts at stair 1.
- Using an operation of the first type, she goes down 1 stair to reach stair 0.
- Using an operation of the second type, she goes up 20 stairs to reach stair 1.
- Using an operation of the first type, she goes down 1 stair to reach stair 0.
Example 2:
Input: k = 1
Output: 4
Explanation:
The 4 possible ways of reaching stair 1 are:
- Alice starts at stair 1. Alice is at stair 1.
- Alice starts at stair 1.
- Using an operation of the first type, she goes down 1 stair to reach stair 0.
- Using an operation of the second type, she goes up 20 stairs to reach stair 1.
- Alice starts at stair 1.
- Using an operation of the second type, she goes up 20 stairs to reach stair 2.
- Using an operation of the first type, she goes down 1 stair to reach stair 1.
- Alice starts at stair 1.
- Using an operation of the first type, she goes down 1 stair to reach stair 0.
- Using an operation of the second type, she goes up 20 stairs to reach stair 1.
- Using an operation of the first type, she goes down 1 stair to reach stair 0.
- Using an operation of the second type, she goes up 21 stairs to reach stair 2.
- Using an operation of the first type, she goes down 1 stair to reach stair 1.
Constraints:
0 <= k <= 109
Solutions
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)
.
The calculation process of the function dfs(i, j, jump)
is as follows:
- If $i > k + 1$, since we cannot go down twice in a row, we cannot reach the $k$th step again, so return $0$;
- If $i = k$, it means that we have reached the $k$th step. The answer is initialized to $1$, and then continue to calculate;
- If $i > 0$ and $j = 0$, it means that we can go down, recursively calculate
dfs(i - 1, 1, jump)
; - Recursively calculate
dfs(i + 2^{jump}, 0, jump + 1)
, and add it to the answer.
To avoid repeated calculations, we use memoization search to save the calculated states.
The time complexity is $O(\log^2 k)$, and the space complexity is $O(\log^2 k)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|