首页 > 试题广场 >

跳跃游戏(一)

[编程题]跳跃游戏(一)
  • 热度指数：8489 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置，则输出true，否则输出false。
数据范围:


输入描述:
第一行输入一个正整数 n ，表示数组 nums 的长度
第二行输入 n 个整数表示数组的每个元素


输出描述:
输出 true 或者 false
示例1

输入

7
2 1 3 3 0 0 100

输出

true

说明

首先位于nums[0]=2，然后可以跳2步，到nums[2]=3的位置，再跳到nums[3]=3的位置，再直接跳到nums[6]=100，可以跳到最后，输出true  
示例2

输入

7
2 1 3 2 0 0 100

输出

false

说明

无论怎么样，都跳不到nums[6]=100的位置  
算法知识视频讲解
开通博客
头像 fred-coder
发表于 2022-02-22 10:58:51
如果给定的数据长度较小，可以采用动态规划，设置 dp, dp[i] 表示 是否可以调到该位置; 状态转移方程为 dp[i] = dp[j] and data[j] + j >= i j < i,由于数据的长度较大，双重循环遍历会超时,采用贪心策略，从后向前遍历数组，看当前位置 + 值 是 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 1eHz
发表于 2024-10-28 00:05:30
关键词：贪心算法、动态规划动态规划解法：核心思想：动态规划解决，维护一个dp数组，其中dp[i]表示到达索引i时能到达的最远距离。解题步骤：创建大小为n的dp数组，初始值设为-1，表示这些位置不可达。初始化状态，设置dp[0]为nums[0]，即从起始位置能到达的最远距离。对于每一个索引i（从1到n 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客262968463号
发表于 2023-06-02 08:38:42
#此题利用动态规划思路 a=int(input()) #取出数组长度 b=[int(i) for i in input().split()] #取出数组内容 if len(b)==1: #如果数组只有1的长度，那必然已经在终点 print("true") else: #创建dp数组，0代 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 DizhX
发表于 2022-02-19 16:13:11
// 方法一：保存布尔型dp数组表示该格子能否到达 import java.util.Scanner;   public class Main{           pu 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 晚风做酒
发表于 2022-03-09 15:47:30
参考LK上大佬的代码； int main() { int n,i , k = 0;  //  k表示最远能到达的距离；     cin>>n; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 lhp_zml
发表于 2024-10-22 11:27:29
#include<iostream> #include<queue> using namespace std; const int N=2e5+6; int arr[N]; int n; bool vis[N]; // 下标是否被访问过 queue<int> q 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 赫he
发表于 2023-07-13 20:08:57
记录最远可以到达的地方，在遍历每个nums时，更新最远的距离 #include <iostream> using namespace std; const int N = 2e5+10; int a[N]; int n; int main() { scanf("%d&q 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 乐弦之佩
发表于 2022-11-24 19:37:27
import java.util.*; public class Main { public static void main(String[] args) { // 标准输入 Scanner input = new Scanner(System.in); 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客238088962号
发表于 2022-10-30 10:28:00
该题用动态规划法求解的核心思想是由终点向起点回推（如果由起点向终点的话，笔者才疏学浅，只想到了穷举一种方法），条件为j-k<=a[k]，即由k点到j点的距离小于a[k]跳动的最大距离，j点为靠后的那一个点。由于数组中任意一点a[k]的值为k点能跳动的最大值，故只要从想要到达的那个点由后向前寻找 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 重生之我要当分子
发表于 2024-12-18 22:44:38
解题思路 这是一个判断能否跳到数组末尾的问题，可以通过贪心算法来解决： 维护一个变量 ，表示当前能够到达的最远位置 遍历数组，对于每个位置 ： 如果 超过了 ，说明无法到达该位置，返回 更新 如果能遍历完整个数组，说明可以到达末尾 代码 cpp java python 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
14条回答 2152浏览

热门推荐

通过挑战的用户

查看代码

相关试题

跳跃游戏(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号