题解 | 跳跃游戏(二)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();

        String line = in.nextLine();
        String[] str = line.split(" ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(str[i]);
        }

        if (n == 1) {
            System.out.println(nums[0]); // 如果只有一个元素，直接输出
            in.close();
            return;
        }

        int score = nums[n - 1];
        int maxIndex = n - 1;
        
        //从倒数第二个位置向前遍历
        for(int i = n - 2; i >= 0; i--) {
            if(i + nums[i] >= maxIndex) {//如果可以从 i 跳到maxIndex
                score += nums[i];
                maxIndex = i;
            }
        }

        // 判断是否到达起点
        int res = maxIndex == 0 ? score : -1;
        System.out.println(res); // 如果只有一个元素，直接输出
        in.close();
    }
    
}

贪心+倒推