周赛250519

终于终于AK了一场😆

第四题100298. 到达第 K 级台阶的方案数

题目大意

给定一个非负整数 k，表示目标台阶的编号。虎老师从台阶 1 开始，通过一系列操作到达台阶 k。操作分为两种：

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

目标是计算虎老师到达台阶 k 的总方案数。

实现思路

1. 定义递归函数：定义一个递归函数 dfs(p, j, f)，其中 p 表示当前所在的台阶，j 表示当前 jump 的次数，f 表示上一次操作是否是向下走一级的标志。
2. 递归终止条件：
   • 当 p == k 时，表示已经到达目标台阶，返回 1 表示找到一种方案。
   • 当 p < 0 时，表示超出范围，返回 0。
   • 当 p - 1 > k 或者 p - 1 == k 且 f == 1 时，表示向下走超过目标或在目标时无法向下走，返回 0。
3. 递归计算：
   • up：计算向上走到 p + 2^j 的方案数，并将 j 加 1，表示使用了一次向上跳跃。
   • down：计算向下走到 p - 1 的方案数，当 p > 0 且 f == 0 时才可以向下走。
   • 返回 up + down + more 的和，其中 more 表示当前正好在目标台阶的情况。
4. 记忆化搜索：使用 @cache 修饰递归函数，避免重复计算。

class Solution:
    def waysToReachStair(self, k: int) -> int:
        
        @cache
        def dfs(p, j, f): # flag 1: 上一次是下移， 0：上一次不是
            more = 0
            if p == k:
                more = 1
                
            if p < 0:
                return 0
            if p-1>k or (p-1==k and f==1):
                return 0

            up = dfs(p + (1 << j), j + 1, 0)

            if p > 0 and f==0:
                down = dfs(p - 1, j, 1)
            else:
                down = 0
            return up + down + more

        return dfs(1, 0, 0)