跳跃游戏(二)

[编程题]跳跃游戏(二)

热度指数：3080 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。

1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1

2.如果无法跳跃(即数组长度为0)，也请返回-1

3.数据保证返回的结果不会超过整形范围，即不会超过 $2^{31}-1$

数据范围:

$0<=nums.length<= 10^5$

$0<=nums[i]<=1000\$

输入描述:

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

输出描述:

输出能获得的最多的积分

示例1

输入

6
2 4 2 1 0 100

输出

说明

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

示例2

输入

6
2 4 0 2 0 100

输出

说明

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

示例3

输入

6
2 3 2 1 0 100

输出

-1

说明

跳不到最后一个位置，返回-1

算法知识视频讲解

Python 3

牛客555680711号

python3 前推法

时间复杂度O(n²)比倒推法O(n)高，但能通过测试。

def solution(n,nums):
    if not n: return -1
    maxL = nums[0]
    dp = [nums[i] for i in range(n)] #以nums[i]为结尾的序列所能获得的maxVal
    for i in range(1,n):
        #1)从nums[0:i)不能到达第i个位置，即当前所能到达的 maxL < i，则无法跳到终点。
        #2)maxL >= i, 则从nums[0:i)某个位置一定能跳到位置i
        if maxL < i: return -1
        maxL = max(maxL, i+nums[i])#更新maxL
        #往回寻找能跳到位置i的最大值位置
        j = i-1 
        #目标位置就是距离位置 i 最近且能到达位置 i 的位置！！
        #假设有且只有k,j都能到达 i，且 k < j < i。则最优解只可能是由k跳到j,再由j跳到i。因为nums值都>=0。
        while(nums[j] + j < i): j -= 1
        #更新以位置i为结尾的序列的maxVal
        dp[i] = max(dp[i],nums[i]+dp[j])
    return dp[-1]

if __name__ == "__main__":
    n = int(input())
    data = list(map(int,input().split()))
    res = solution(n,data)
    print(res)

发表于 2022-07-26 15:41:31 回复(0)

Python 3

铁离子

n = int(input())
nums = list(map(int,input().split(' ')))
idx = n-1
res = 0
while idx>0:
    res += nums[idx]
    j = idx-1
    while j>=0 and nums[j]+j<idx:
        j-=1
    if j<0:
        break
    idx = j
if idx>0:
    print(-1)
else:
    print(res+nums[0])

发表于 2022-07-20 16:34:47 回复(0)