What mistake am I making while memoizing this solution for Leetcode problem jump game 4-CodePudding

So the question is You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i 1, min(n - 1, i k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.

Example 1:

Input: nums = [1,-1,-2,4,-7,3], k = 2 Output: 7 Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

I wrote a recursive solution in which we explore all the possibilies . If the function is called at index ind , then the value at index ind is added to a variable curSum for the next function call. The base condition is when we reach the last index , we will return curSum value of last index.

Here is the code:

class Solution {
    
    static int min= Integer.MIN_VALUE;
    
    public int maxResult(int[] nums, int k) {
        
     return max(nums,0,k,0);
    }
    
    public int max(int [] nums, int ind, int k, int curSum)
    {  
        if(ind==nums.length-1)
            return curSum nums[ind];
   
        int max=Integer.MIN_VALUE;
        
        
        for(int i=ind 1;i<=Math.min(nums.length-1,ind k);i  )
         max=Math.max(max, max(nums,i,k,curSum nums[ind]));
         
        return max;
        
    }
}

Code works fine except the exponential complexity ofcourse.

I tried memoizing it as

class Solution {
     static int[] dp;
    static int min= Integer.MIN_VALUE;
    public int maxResult(int[] nums, int k) {
        
        dp=new int[nums.length];
        Arrays.fill(dp,min);
       
        return max(nums,0,k,0);
    }
    
    public int max(int [] nums, int ind, int k, int curSum)
    {
        
        if(ind==nums.length-1)
            return curSum nums[ind];
            
       if(dp[ind]!=min)
           return dp[ind];
        
        int max=Integer.MIN_VALUE;
        
        for(int i=ind 1;i<=Math.min(nums.length-1,ind k);i  )
          max=Math.max(max, max(nums,i,k,curSum nums[ind]));
        
        return dp[ind]=max;
        
    }
}

But this solution gives the wrong max everytime and I am not quite able to figure out why. Any hints will be appreciated.

Thanks

CodePudding user response：

You only need to memoize dp[index] instead of calling f(index, currSum).

Take for example present arr.length = 5, k = 2 For index-2 you need wether index 3 or 4 gives better points to you irrespective of your present point. Better way would be :

class Solution {
     static int[] dp;
    static int min= Integer.MIN_VALUE;
    public int maxResult(int[] nums, int k) {
        
        dp=new int[nums.length];
        Arrays.fill(dp,min);
       
        return max(nums,0,k,0);
    }
    
    public int max(int [] nums, int ind, int k, int curSum)
    {
        
        // base-case
        if(ind==nums.length-1)
            return curSum nums[ind];
       
       // if already memoized
       if(dp[ind]!=min)
           return dp[ind]   curSum;
        
       // if not memoized, calculate value now
        int max=Integer.MIN_VALUE;
        
        for(int i=ind 1;i<=Math.min(nums.length-1,ind k);i  )
          max=Math.max(max, max(nums,i,k,nums[ind]);
        
        // memoize here 
        dp[ind] = max

        return dp[ind]   curSum;
        
    }
}