摘要
Title: 3154. 到达第 K 级台阶的方案数
Categories: dp

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

题意

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

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

向下走一级到 i - 1 ，但该操作不能连续使用，如果在台阶第 0 级也不能使用。
向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。
请你返回 Alice 到达台阶 k 处的总方案数。

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

思路

记忆化搜索，由于到了目标台阶还可以操作，那么方案的终止就不是等于台阶数，应该是大于目标台阶数，且无法退回来
is_back 表示是否用了后退的机会

代码

'''
Author: NEFU AB-IN
Date: 2024-08-20 15:14:55
FilePath: \LeetCode\3154\3154.py
LastEditTime: 2024-08-20 16:04:34
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def waysToReachStair(self, k: int) -> int:

        @lru_cache(None)
        def dfs(n: int, is_back: bool, jump: int):
            if n - int(not is_back) > k:
                return 0

            res = int(n == k)

            # down first
            if not is_back and n:
                res += dfs(n - 1, True, jump)

            res += dfs(n + 2 ** jump, False, jump + 1)
            return res

        res = dfs(1, False, 0)
        dfs.cache_clear()
        return res