3154. 到达第 K 级台阶的方案数

来源第 398 场周赛 Q4难度困难分数2071

题目描述

给你有一个非负整数 k 。有一个无限长度的台阶，最低一层编号为 0 。

Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用任意次操作，目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次操作中，Alice 可以：

向下走一级到 i - 1 ，但该操作不能连续使用，如果在台阶第 0 级也不能使用。
向上走到台阶 i + 2^jump 处，然后 jump 变为 jump + 1 。

请你返回 Alice 到达台阶 k 处的总方案数。

注意，Alice 可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。

示例 1：

输入：k = 0

输出：2

解释：

2 种到达台阶 0 的方案为：

Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 2⁰ 级台阶到台阶 1 。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。

示例 2：

输入：k = 1

输出：4

解释：

4 种到达台阶 1 的方案为：

Alice 从台阶 1 开始，已经到达台阶 1 。
Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 2⁰ 级台阶到台阶 1 。
Alice 从台阶 1 开始。
- 执行第二种操作，向上走 2⁰ 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。
Alice 从台阶 1 开始。
- 执行第一种操作，从台阶 1 向下走到台阶 0 。
- 执行第二种操作，向上走 2⁰ 级台阶到台阶 1 。
- 执行第一种操作，向下走 1 级台阶到台阶 0 。
- 执行第二种操作，向上走 2¹ 级台阶到台阶 2 。
- 执行第一种操作，向下走 1 级台阶到台阶 1 。

提示：

0 <= k <= 10⁹

解法

方法一：记忆化搜索

思考

两种操作：向下走一格（不能连续），或向上跳 \(2^{jump}\) 并令 \(jump\) 加一。从 \(1\) 出发到达 \(k\) 的方案数。盲目搜索分支随跳次指数增长。

位置一旦超过 \(k+1\) 便无法再下来回到 \(k\)。跳的次数约为 \(O(\log k)\)，状态 \((i,j,jump)\) 很少，其中 \(j\) 标记上次是否刚向下。

记忆化 \(dfs(i,j,jump)\)：到达 \(k\) 先计 \(1\)，允许时向下，并始终尝试上跳。越界返回 \(0\)。

我们设计一个函数 \(\textit{dfs}(i, j, \textit{jump})\)，表示当前位于第 \(i\) 级台阶，且进行了 \(j\) 次操作 \(1\) 和 \(\textit{jump}\) 次操作 \(2\)，到达第 \(k\) 级台阶的方案数。那么答案就是 \(\textit{dfs}(1, 0, 0)\)。

函数 \(\textit{dfs}(i, j, \textit{jump})\) 的计算过程如下：

如果 \(i > k + 1\)，由于无法连续两次向下走，所以无法再到达第 \(k\) 级台阶，返回 \(0\)；
如果 \(i = k\)，表示已经到达第 \(k\) 级台阶，答案初始化为 \(1\)，然后继续计算；
如果 \(i > 0\) 且 \(j = 0\)，表示可以向下走，递归计算 \(\textit{dfs}(i - 1, 1, \textit{jump})\)；
递归计算 \(\textit{dfs}(i + 2^{\textit{jump}}, 0, \textit{jump} + 1)\)，累加到答案中。

为了避免重复计算，我们使用记忆化搜索，将已经计算过的状态保存起来。

时间复杂度 \((\log ^2 k)\)，空间复杂度 \((\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. 到达第 K 级台阶的方案数

题目描述

解法

方法一：记忆化搜索

评论