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

相关文章

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

高效+灵活,万博智云全球发布AWS无代理跨云容灾方案!

摘要 近日,万博智云推出了基于AWS的无代理跨云容灾解决方案,并与拉丁美洲,中东,亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础,将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合,为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日,万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频,介绍了

Android平台播放RTSP流的几种方案探究(VLC VS ExoPlayer VS SmartPlayer)

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候,不知道如何选的好,本文针对常用的方案,做个大概的说明: 1. 使用VLC for Android VLC Media Player(VLC多媒体播放器),最初命名为VideoLAN客户端,是VideoLAN品牌产品,是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式,并支持DVD影音光盘,VCD影

JavaFX应用更新检测功能(在线自动更新方案)

JavaFX开发的桌面应用属于C端,一般来说需要版本检测和自动更新功能,这里记录一下一种版本检测和自动更新的方法。 1. 整体方案 JavaFX.应用版本检测、自动更新主要涉及一下步骤: 读取本地应用版本拉取远程版本并比较两个版本如果需要升级,那么拉取更新历史弹出升级控制窗口用户选择升级时,拉取升级包解压,重启应用用户选择忽略时,本地版本标志为忽略版本用户选择取消时,隐藏升级控制窗口 2.

如何选择SDR无线图传方案

在开源软件定义无线电(SDR)领域,有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案: 1. **OpenHD**:这是一个远程高清数字图像传输的开源解决方案,它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链,包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP(Universal Software Radio Periphera

MyBatis 切换不同的类型数据库方案

下属案例例当前结合SpringBoot 配置进行讲解。 背景: 实现一个工程里面在部署阶段支持切换不同类型数据库支持。 方案一 数据源配置 关键代码(是什么数据库,该怎么配就怎么配) spring:datasource:name: test# 使用druid数据源type: com.alibaba.druid.pool.DruidDataSource# @需要修改 数据库连接及驱动u

一种改进的red5集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

转自: 一种改进的red5集群方案的应用: http://wenku.baidu.com/link?url=jYQ1wNwHVBqJ-5XCYq0PRligp6Y5q6BYXyISUsF56My8DP8dc9CZ4pZvpPz1abxJn8fojMrL0IyfmMHStpvkotqC1RWlRMGnzVL1X4IPOa_  基于Red5服务器集群负载均衡调度算法研究 http://ww

家庭和学生用户笔记本电脑配置方案

2.6.1  家庭和学生用户笔记本电脑配置方案   2.6.1  家庭和学生用户笔记本电脑配置方案   普通家庭用户、学生用户主要用于上网、娱乐、学习等,这类用户要求笔记本电脑的各方面 功能比较均衡。在选购此类笔记本电脑时,主要考虑外观设计方面要比较时尚,而且性能上也要 够强,一些大型复杂的软件以及目前的主流游戏都要能够流畅地运行才行。   对于CPU方面,可以考虑目前主流的第二

【信创建设】信息系统信创建设整体技方案(word原件完整版)

信创,即“信息技术应用创新”。我国自主信息产业聚焦信息技术应用创新,旨在通过对IT硬件、软件等各个环节的重构,基于我国自有IT底层架构和标准,形成自有开放生态,从根本上解决本质安全问题,实现信息技术可掌控、可研究、可发展、可生产。信创发展是一项国家战略,也是当今形势下国家经济发展的新功能。信创产业发展已经成为各行各业数字化转型、提升产业链发展的关键。 软件全套资料部分文档清单: 工作安排任

【QNX+Android虚拟化方案】120 - Android 侧 USB2.0 插拔过程

【QNX+Android虚拟化方案】120 - Android 侧 USB2.0 插拔过程 基于原生纯净代码,自学总结 纯技术分享,不会也不敢涉项目、不泄密、不传播代码文档!!! 本文禁止转载分享 !!! 汇总链接:《【QNX+Android虚拟化方案】00 - 系列文章链接汇总》 本文链接:《【QNX+Android虚拟化方案】120 - Android 侧 USB2.0