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