题解 | #跳跃游戏(二)#

本题如果用动态规划,可能会超时,采用贪心的策略,从后往前遍历数组,记录可到达当前点的最大消耗值,最终判断是否可从初始点到达

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def maxJumpGrade(self , nums: List[int]) -> int:
        # write code here
        n = len(nums)
        if n == 0: return -1
        if n == 1: return nums[0]
        start = n - 1
        base = 0
        for i in range(n - 1, -1, -1):
            # 可以省略
            last = base
            if i + nums[i] >= start:
                start = i
                # 由于每个值都是 >= 0 的,求的是最大值，即多走消耗比少走的多, 此处可以直接加
                base = max(base, last + nums[i])
        return base if start == 0 else -1