↓Skip to main content
  1. Posts/

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

·2 mins·
Table of Contents

LeetCode-3154 到达第 K 级台阶的方案数 #

Solution 1 #

本题的状态非常明确: 当前在第 $k$ 级, 当前 $jump$, 下一步是否允许 $down$ . 从可能的状态转移过来即可.

代码如下:

class Solution:
    import math
    def waysToReachStair(self, k: int) -> int:
        MAXE = int(log(1e10, 2)) + 1
        
        @cache
        def f(i, jump, down):
            if down == 0:
                if jump >= 1:
                    return f(i - (1 << (jump - 1)), jump - 1, 0) + f(i - (1 << (jump - 1)), jump - 1, 1)
                else:
                    return 1 if i == 1 else 0
            return f(i + 1, jump, 0)

        return sum([f(k, jump, 0) for jump in range(MAXE)] + [f(k, jump, 1) for jump in range(MAXE)] )

也可以定义成从 $k$ 出发, 初始为 $jump$, 上一步是否 $down$ 过.

参考灵茶山艾府的代码:

class Solution:
    def waysToReachStair(self, k: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, pre_down: bool) -> int:
            if i > k + 1:  # 无法到达终点 k
                return 0
            res = 1 if i == k else 0
            res += dfs(i + (1 << j), j + 1, False)  # 操作二
            if i and not pre_down:
                res += dfs(i - 1, j, True)  # 操作一
            return res
        return dfs(1, 0, False)

Solution 2 #

假设使用了 $m$ 次下降, $n$ 次上升, 那么有 $1 + 2^0+\dots + 2^{n - 1} - m = k$ , 有 $m = 2^n - k$ . 需要把 $m$ 次下降插入到 $n$ 次上升中, 且不能有连续两次下降, 等价于从 $n + 1$ 个空隙中选出 $m$ 个, 方法数为 $\binom{n + 1}{m}$ . 枚举可能的 $m$ 和 $n$ 并求和.

代码如下:

class Solution:
    def waysToReachStair(self, k: int) -> int:
        ans = 0
        for n in range(30):
            m = (1 << n) - k
            if 0 <= m <= n + 1:
                ans += comb(n + 1, m)
        return ans
↑