题目描述

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

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

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

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

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

样例

输入：k = 0

输出：2

解释：

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

虎老师从台阶 1 开始。
    执行第一种操作，从台阶 1 向下走到台阶 0。

虎老师从台阶 1 开始。
    执行第一种操作，从台阶 1 向下走到台阶 0。
    执行第二种操作，向上走 2^0 级台阶到台阶 1。
    执行第一种操作，从台阶 1 向下走到台阶 0。

输入：k = 1

输出：4

解释：

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

虎老师从台阶 1 开始，已经到达台阶 1。

虎老师从台阶 1 开始。
    执行第一种操作，从台阶 1 向下走到台阶 0。
    执行第二种操作，向上走 2^0 级台阶到台阶 1。

虎老师从台阶 1 开始。
    执行第二种操作，向上走 2^0 级台阶到台阶 2。
    执行第一种操作，向下走 1 级台阶到台阶 1。

虎老师从台阶 1 开始。
    执行第一种操作，从台阶 1 向下走到台阶 0。
    执行第二种操作，向上走 2^0 级台阶到台阶 1。
    执行第一种操作，向下走 1 级台阶到台阶 0。
    执行第二种操作，向上走 2^1 级台阶到台阶 2。
    执行第一种操作，向下走 1 级台阶到台阶 1。

限制

• 0 <= k <= 10^9

算法

(思维题) $O(\log^2 k)$

1. 注意到，如果确定了向上走的次数 $jump$，则向上的走的台阶数就是 $2^{jump - 1} - 1$。
2. 如果向上走了 $jump$ 次，则可以下降的台阶数最多为 $jump + 1$。
3. 所以，在给定向上走的次数 $jump$ 后，如果最终到达的位置，距离 $k$ 的值 $d$，满足 $0 \le d \le k$，则可以通过下降来到达 $k$。
4. 其方案数就是组合数 $C_{jump + 1}^{jump + 1 - d}$。
5. 注意特殊处理一次都不使用 $jump$ 的情况，即当 $k \le 1$ 时，方案数需要额外加一。

时间复杂度

• 预处理组合数的时间复杂度为 $O(\log^2 k)$。
• 求解答案的时间复杂度为 $O(\log k)$。
• 故总时间复杂度为 $O(\log^2 k)$。

空间复杂度

• 需要 $O(\log^2 k)$ 的额外空间存储组合数。

C++ 代码

int c[31][31];

auto init = []{
    for (int i = 0; i < 31; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }

    return 0;
}();

class Solution {
public:
    int waysToReachStair(int k) {
        int ans = (k <= 1);

        for (int jump = 1; jump < 30; jump++) {
            int d = (1 << jump) - k;

            if (d >= 0 && d <= jump + 1)
                ans += c[jump + 1][jump + 1 - d];
        }

        return ans;
    }
};