跳跃游戏二：

有没有人感觉牛客网的题解都是只上代码，不给思路的。只上代码总觉得是在直接抄答案。 这道题我先找了leetcode发现没有这道题。于是我想到了leetcode的跳跃游戏一的视频题解。上面说到了方法2用倒推的方式。我们在这道题上用倒推变形。 首先最后一个数组元素一定是包含在最大分数中的。然后就考虑前面的每个是否能到达最后一个位置。如果能的话将pos向前推，只考虑当前跳跃位置能不能跳到pos。最初pos在n-1位置，即最终位置。随着往前遍历，pos也跟着往前。

比如1,2,3,0,0,1,4数组中：最终位置为数组下标6（arr[6]）位置。考虑下标5位置能不能到，5可以到6，所以pos更新成5.再往前看有没有能到5的位置。能到5就能到6. 能到的就把当前位置值加到最大分数中。因为我们遍历了每个下标，不能到的都没加到最大分数res中，那么最终我们判断一下pos是否到了0位置，如果到了，说明可以从0到下标6位置。得到的res就是最大分数。如果pos不能到0位置。则说明0位置不能到6位置。

public class Main{
    public static int process(int[]arr,int n){
        int pos=n-1;
        int res=arr[pos];
        for(int i=n-2;i>=0;i--){
            if(arr[i]+i>=pos){
                pos=i;
                res+=arr[i];
            }
        }
        if(pos==0)
            return res;
        return -1;
    }
    
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        if(n==0)
            System.out.print(-1);
        else{
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            System.out.print(process(arr,n));
        }
    }
}