0动态规划中等 NC206 跳跃游戏(二)

NC206 跳跃游戏(二)

描述

给定一个非负整数数组nums，假定最开始处于下标为0的位置，数组里面的每个元素代表下一跳能够跳跃的最大长度，如果可以跳到数组最后一个位置，请你求出跳跃路径中所能获得的最多的积分。
1.如果能够跳到数组最后一个位置，才能计算所获得的积分，否则积分值为-1
2.如果无法跳跃(即数组长度为0)，也请返回-1
3.数据保证返回的结果不会超过整形范围，即不会超过2^{31}-12
31 −1

分析

要解决两个问题：1.能不能走到最后一个元素；2.积分最大。
使用跳跃游戏一的贪心方法可以判断是否能够走到最后一个元素，但是不清楚要走那条才是积分最大的，不好解决第二个问题。
从后向前的动态规划可以轻易解决问题1，2。
1.能不能走到最后一个元素：
首先看倒数第二个能否走到最后一个元素，然后看倒数第三个元素能否走到倒数第二个，或者直接走到最后一个元素。也就是说一个元素在其能够跳跃到的范围内是否有一个元素调到最后一个元素，如果有，则这个元素是可以调到最后一个元素的，如果不可以，则这个元素不能调到最后一个元素。
2.积分最大：
贪心思想，经可能的多跳，因为是非负的，所以跳的越多，积分越多。一个元素应该选择距离他最近的元素跳，这样跳的次数更多，经过的元素的个数越多，积分越大。

import java.util.*;
public class Solution {
    public int maxJumpGrade (int[] nums) {
        int n = nums.length;
        if(n == 0){
            return -1;
        }
        int[] dp = new int[n];
        Arrays.fill(dp,-1);
        dp[n-1] = nums[n-1];
        for(int i = n - 2; i >= 0; i--){
            if(nums[i] == 0){
                continue;
            }
            for(int j = i+1; j < n && j <= i+nums[i]; j++){
                if(dp[j] != -1){
                    dp[i] = dp[j] + nums[i];
                    break;
                }
            }
        }
        return dp[0];
    }
}