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

链接：3154.到达第K级台阶的方案数
难度：Hard
标签：位运算、记忆化搜索、数学、动态规划、组合数学
简介：请你返回 Alice 到达台阶 k 处的总方案数。

题解 1 - python

• 编辑时间：2024-08-20
• 执行用时：138ms
• 内存消耗：18.18MB
• 编程语言：python
• 解法介绍：dp遍历

class Solution:
    def waysToReachStair(self, k: int) -> int:
        @cache
        def dfs(cur: int, jump: int, down: bool) -> int:
            if cur > k + 1: return 0
            res = 0
            if cur == k: res += 1
            res += dfs(cur + 2 ** jump, jump + 1, False)
            if cur != 0 and not down: res += dfs(cur - 1, jump, True)
            return res
        return dfs(1, 0, False)