首页 > 试题广场 >

跳跃游戏(二)

[编程题]跳跃游戏(二)
  • 热度指数：3080 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。
1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1
2.如果无法跳跃(即数组长度为0)，也请返回-1
3.数据保证返回的结果不会超过整形范围，即不会超过
数据范围:




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


输出描述:
输出能获得的最多的积分
示例1

输入

6
2 4 2 1 0 100

输出

106

说明

首先位于nums[0]=2，然后可以跳1步，到nums[1]=4的位置，积分=2+4=6，再跳到nums[5]=100的位置，积分=6+100=106
这样保证既能跳到数组最后一个元素，又能保证获取的积分最多    
示例2

输入

6
2 4 0 2 0 100

输出

108

说明

跳跃路径为：2=>4=>2=>100，总共为108       
示例3

输入

6
2 3 2 1 0 100

输出

-1

说明

跳不到最后一个位置，返回-1      
算法知识视频讲解
开通博客
头像 牛客687146177号
发表于 2022-05-25 09:21:51
跳跃游戏二： 有没有人感觉牛客网的题解都是只上代码，不给思路的。只上代码总觉得是在直接抄答案。 这道题我先找了leetcode发现没有这道题。于是我想到了leetcode的跳跃游戏一的视频题解。上面说到了方法2用倒推的方式。我们在这道题上用倒推变形。 首先最后一个数组元素一定是包含在最大分数中的。然 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 牛客831486771号
发表于 2023-02-08 16:42:23
第一种方法是DP函数通过递归加回溯，从0位置从前往后找出所有能够到达终点的路径，将结果累加到sum中，若能到达终点且sum>max就赋值给max，但是复杂度过大pass掉了。 第二种方法是通过从后向前的循环，找出能走通的每一个节点并进行累加，就是这么简单。。。。。。 #include < 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Coming680
发表于 2022-03-02 19:50:25
#include<iostream> using namespace std; int dp[100000]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; bool ans = 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客338956253号
发表于 2023-02-08 01:38:55
#include <iostream> #include <vector> using namespace std; int main() { int n; while (cin >> n) { vector<int> 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 卢然小子
发表于 2022-07-17 10:47:11
描述 给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。 1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1 2.如果无法跳跃(即数组长度为0)，也请 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客356358940号
发表于 2022-05-25 15:00:14
https://www.nowcoder.com/questionTerminal/58e31b785f4b4ced9695dd4fcd60c1ce 属于第一题的衍生，多设置一个参数score存放nums的值，当满足题意时将nums值叠加到score的结果中 class Sol 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛1452
发表于 2023-11-23 13:46:49
此题利用动态规划思路根据第一问我们从后向前遍历（倒数第二位开始）我们比较每一位数是否大于该点到终点的距离若大于则更新终点为该点，如不大于则跳过继续向前遍历，这样我们把可以作为终点的点在dp数组里面记为1否则记为0，然后通过dp数组的下标对应输入的数组下标，所以我们找到了数组中对应的元素，然后加上终点 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 静寂旮旯
发表于 2022-04-29 14:41:47
解题思路： 不能递归了，递归栈真的会炸。 递推进行，不能常规地从左往右推，而应该从右往左推，即答案位于dp[0]。 先讨论一般情况，dp[i]表达的是此位置能到达n-1位置所能得到的最大分数。那么对于任一位置i有：dp[i]=max(dpi+1:n−1+v[i])dp[i] = max(dp_{i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客555680711号
发表于 2022-07-26 15:39:11
python3 前向DP版本，时间复杂度O(n2)比倒推法O(n)要高，但可以通过测试。 def solution(n,nums):     if not n: return -1  & 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 赫he
发表于 2023-07-14 20:33:12
如果最大分数存在，最后一个数一定在里面初始化pos为n-1，不断向前遍历，看遍历到的位置i能否跳到pos，能说明从 i 最终可以跳到最后。如果i遍历过了0，而pos还未更新到0，说明数组不能跳到最后。举个例子：[1,2,3,0,0,1,4]，n=7。初始pos = 6 -> i=5，nums[ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
9条回答 1331浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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