A25647. 青蛙跳格子编程实现有 71 个大小相等的格子从左到右排成一排，编号从 0 到 70，其中 N 个格子有荷叶，初始时青蛙在编号为 0 的格子。青蛙要按照以下规则，跳到最后一个有荷叶的格子：1、青蛙每次最少跳 1 格，最多跳 x 格；2、青蛙每次只能跳到有荷叶的格子；3、青蛙不能往回跳。给定 N 个有荷叶的格子编号，以及青蛙每次最多可以跳的格子数 x。请计算青蛙一共有多少种不同的方式跳到最后一个有荷…
填空题
中等
知识点
题目描述
青蛙跳格子
编程实现
有 71 个大小相等的格子从左到右排成一排，编号从 0 到 70，其中 N 个格子有荷叶，初始时青蛙在编号为 0 的格子。青蛙要按照以下规则，跳到最后一个有荷叶的格子：
1、青蛙每次最少跳 1 格，最多跳 x 格；
2、青蛙每次只能跳到有荷叶的格子；
3、青蛙不能往回跳。
给定 N 个有荷叶的格子编号，以及青蛙每次最多可以跳的格子数 x。请计算青蛙一共有多少种不同的方式跳到最后一个有荷叶的格子，如果青蛙不能跳到最后一个有荷叶的格子，输出 0。
例如：N = 4，x = 3，4 个有荷叶的格子编号依次为 1、3、4、6，青蛙每次最多跳 3 格；
青蛙有以下不同的方式跳到最后一个有荷叶的格子（6 号格子）：
第一种：先跳到编号 1 的格子，接着跳到编号 3 的格子，再跳到编号 4 的格子，最后跳到编号 6 的格子；
第二种：先跳到编号 1 的格子，再跳到编号 3 的格子，最后跳到编号 6 的格子；
第三种：先跳到编号 1 的格子，再跳到编号 4 的格子，最后跳到编号 6 的格子；
第四种：先跳到编号 3 的格子，再跳到编号 4 的格子，最后跳到编号 6 的格子；
第五种：先跳到编号 3 的格子，最后跳到编号 6 的格子。
青蛙一共有 5 种不同的方式跳到最后一个有荷叶的格子。
输入描述
第一行输入一个整数 N（3 ≤ N ≤ 30），表示有荷叶的格子数
第二行按从小到大的方式输入 N 个互不相同的整数（1 ≤ 整数 ≤ 70），表示有荷叶的格子编号，整数之间以一个空格隔开
第三行输入一个整数 x（1 ≤ x ≤ 5），表示青蛙每次最多可以跳的格子数
输出描述
输出一个整数，表示青蛙一共有多少种不同的方式跳到最后一个有荷叶的格子
样例输入
4
1 3 4 6
3样例输出
5参考答案
n = int(input().strip())
positions = list(map(int, input().split()))
x = int(input().strip())
# 确保 positions 是排序的，输入说按从小到大
# dp[j] 表示跳到第 j 个荷叶格子的方式数
dp = [0] * n
for j in range(n):
# 检查是否可以从0直接跳到 positions[j]
if 1 <= positions[j] <= x: # 因为从0开始，距离为 positions[j]
dp[j] = 1
else:
dp[j] = 0
# 从之前的荷叶格子跳
for i in range(j): # i 从 0 到 j-1
dist = positions[j] - positions[i]
if 1 <= dist <= x:
dp[j] += dp[i]
print(dp[n-1]) # 输出跳到最后一个荷叶格子的方式数
上一题
下一题