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 + 2^jump. 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:

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 2⁰ 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 2⁰ stairs to reach stair 1.
Alice starts at stair 1.
- Using an operation of the second type, she goes up 2⁰ 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 2⁰ 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 2¹ stairs to reach stair 2.
- Using an operation of the first type, she goes down 1 stair to reach stair 1.

Constraints:

0 <= k <= 10⁹

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)$.

Python3JavaC++GoTypeScript

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)

class Solution {
    private Map<Long, Integer> f = new HashMap<>();
    private int k;

    public int waysToReachStair(int k) {
        this.k = k;
        return dfs(1, 0, 0);
    }

    private int dfs(int i, int j, int jump) {
        if (i > k + 1) {
            return 0;
        }
        long key = ((long) i << 32) | jump << 1 | j;
        if (f.containsKey(key)) {
            return f.get(key);
        }
        int ans = i == k ? 1 : 0;
        if (i > 0 && j == 0) {
            ans += dfs(i - 1, 1, jump);
        }
        ans += dfs(i + (1 << jump), 0, jump + 1);
        f.put(key, ans);
        return ans;
    }
}

class Solution {
public:
    int waysToReachStair(int k) {
        unordered_map<long long, int> f;
        auto dfs = [&](this auto&& dfs, int i, int j, int jump) -> int {
            if (i > k + 1) {
                return 0;
            }
            long long key = ((long long) i << 32) | jump << 1 | j;
            if (f.contains(key)) {
                return f[key];
            }
            int ans = i == k ? 1 : 0;
            if (i > 0 && j == 0) {
                ans += dfs(i - 1, 1, jump);
            }
            ans += dfs(i + (1 << jump), 0, jump + 1);
            f[key] = ans;
            return ans;
        };
        return dfs(1, 0, 0);
    }
};

func waysToReachStair(k int) int {
    f := map[int]int{}
    var dfs func(i, j, jump int) int
    dfs = func(i, j, jump int) int {
        if i > k+1 {
            return 0
        }
        key := (i << 32) | jump<<1 | j
        if v, has := f[key]; has {
            return v
        }
        ans := 0
        if i == k {
            ans++
        }
        if i > 0 && j == 0 {
            ans += dfs(i-1, 1, jump)
        }
        ans += dfs(i+(1<<jump), 0, jump+1)
        f[key] = ans
        return ans
    }
    return dfs(1, 0, 0)
}

function waysToReachStair(k: number): number {
    const f: Map<bigint, number> = new Map();

    const dfs = (i: number, j: number, jump: number): number => {
        if (i > k + 1) {
            return 0;
        }

        const key: bigint = (BigInt(i) << BigInt(32)) | BigInt(jump << 1) | BigInt(j);
        if (f.has(key)) {
            return f.get(key)!;
        }

        let ans: number = 0;
        if (i === k) {
            ans++;
        }

        if (i > 0 && j === 0) {
            ans += dfs(i - 1, 1, jump);
        }

        ans += dfs(i + (1 << jump), 0, jump + 1);
        f.set(key, ans);
        return ans;
    };

    return dfs(1, 0, 0);
}

3154. Find Number of Ways to Reach the K-th Stair

Description

Solutions

Solution 1: Memoization Search

Comments