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

2024-08-20 18:12
文章标签 台阶 方案 到达 3154

本文主要是介绍3154. 到达第 K 级台阶的方案数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Powered by:NEFU AB-IN

Link

文章目录

  • 3154. 到达第 K 级台阶的方案数
    • 题意
    • 思路
    • 代码

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 0res = int(n == k)# down firstif not is_back and n:res += dfs(n - 1, True, jump)res += dfs(n + 2 ** jump, False, jump + 1)return resres = dfs(1, False, 0)dfs.cache_clear()return res

这篇关于3154. 到达第 K 级台阶的方案数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1090807

相关文章

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提

Python实现html转png的完美方案介绍

《Python实现html转png的完美方案介绍》这篇文章主要为大家详细介绍了如何使用Python实现html转png功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 1.增强稳定性与错误处理建议使用三层异常捕获结构:try: with sync_playwright(

Java使用多线程处理未知任务数的方案介绍

《Java使用多线程处理未知任务数的方案介绍》这篇文章主要为大家详细介绍了Java如何使用多线程实现处理未知任务数,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 知道任务个数,你可以定义好线程数规则,生成线程数去跑代码说明:1.虚拟线程池:使用 Executors.newVir

MySQL中闪回功能的方案讨论及实现

《MySQL中闪回功能的方案讨论及实现》Oracle有一个闪回(flashback)功能,能够用户恢复误操作的数据,这篇文章主要来和大家讨论一下MySQL中支持闪回功能的方案,有需要的可以了解下... 目录1、 闪回的目标2、 无米无炊一3、 无米无炊二4、 演示5、小结oracle有一个闪回(flashb

Android App安装列表获取方法(实践方案)

《AndroidApp安装列表获取方法(实践方案)》文章介绍了Android11及以上版本获取应用列表的方案调整,包括权限配置、白名单配置和action配置三种方式,并提供了相应的Java和Kotl... 目录前言实现方案         方案概述一、 androidManifest 三种配置方式

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每