LeetCode 1696. Jumping game VI daily question

Problem description

I'll give you a subscript from 0 The starting array of integers nums  And an integer k .

At first you were subscribing  0  It's about . Each step , You can jump forward at most  k  Step , But you can't jump out of the bounds of an array . in other words , You can start with the subscript  i  Jump to the  [i + 1, min(n - 1, i + k)]  contain Any position of the two endpoints .

Your goal is to get to the last position in the array （ Subscript to be n - 1 ）, Yours score   Is the sum of all the numbers passed .

Please return to what you can get Maximum score  .

Example 1：

Input ：nums = [1,-1,-2,4,-7,3], k = 2
Output ：7
explain ： You can choose subsequences [1,-1,4,3] （ The numbers in bold above ）, And for 7 .
Example 2：

Input ：nums = [10,-5,-2,4,0,3], k = 3
Output ：17
explain ： You can choose subsequences [10,4,3] （ It's bold ）, And for 17 .
Example 3：

Input ：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output ：0
 

Tips ：

 1 <= nums.length, k <= 105
-104 <= nums[i] <= 104

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/jump-game-vi
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

java

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MIN_VALUE);
        dp[0] = nums[0];

        for(int i = 0;i < n;i++){
            // jump k Time 
            for(int j = i + 1;j < n && j <= i + k;j++){
                // Score after jump 
                int nextScore = dp[i] + nums[j];
                // Update to a higher score after jumping 
                if(nextScore > dp[j]) dp[j] = nextScore;
                // Filter 
                if(dp[j] >= dp[i]) break;
            }
        }
        return dp[n - 1];
    }
}