Return correct value at each iteration- dynamic programming

Question

The problem goes like this:

Geek is going for n day training program. He can perform any one of these three activities Running, Fighting, and Learning Practice. Each activity has some point on each day. As Geek wants to improve all his skills, he can't do the same activity on two consecutive days. Help Geek to maximize his merit points as you are given a 2D array of points points, corresponding to each day and activity.

Now this is how i'm trying to approach. I take each of the value of the array and recursively call on the next index while passing the previous index so as to skip its value in the calculation.

I'm getting it wrong because I'm returning this.currentMax which keeps getting added to points[index][j] whereas what I'd rather want is at each step the calculations happen for that iterations only and if it's bigger than this.currentMax the latter should get updated. How can I correct that? Appreciate any help.

class Solution {
    //Function to find the maximum points among all the possible ones.
    currentMax = -Infinity;
    maximumPoints(points, n, index=0, prev=-1)
    {
        if(index === n) return 0;
        for(var j=0; j<points[index].length; j++){
          //skip the prev index
          if(j !== prev){
           var temp = points[index][j] + this.maximumPoints(points, n, index+1, j);
           
           this.currentMax = Math.max(this.currentMax, temp);
           
          }
            
         }
        
        return this.currentMax //This is where perhaps going wrong
    }
}

var x = new Solution();
console.log(x.maximumPoints([[1,2,5], [6, 2, 10]], 2))

EDIT: @Bergi's suggestions work. But here's what's still confuses me. When we make a local variable, maxPoint, shoudn't the next recursive call reset this variable to 0 again and again.

For e.g, f(([[1,2,5], [6, 2, 10]], 2, index=0, prev=-1) would generate

1+ f(([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)
2 + f(([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)
5 + f(([[1,2,5], [6, 2, 10]], 2, index=1, prev=0)

But in each of these calls the maxPoint would be updated with Max of what's returned and 0(zero since each gets reset everytime?)

Appreciate clarifications:

class Solution {
    //Function to find the maximum points among all the possible ones.
   
    maximumPoints(points, n, index=0, prev=-1)
    {
        if(index === n) return 0;
        let maxPoint = 0;
        
        for(var j=0; j<points[index].length; j++){
          //skip the prev index
          if(j !== prev){
           var temp = points[index][j] + this.maximumPoints(points, n, index+1, j);
           
           maxPoint = Math.max(maxPoint, temp);
           
          }
            
         }
        
        return maxPoint;
    }
}

var x = new Solution();
console.log(x.maximumPoints([[1,2,5], [6, 2, 10]], 2))

Answer 1

As you indicate the immediate problem is that this.currentMax keeps being added to and never rolls back to a previous value when you backtrack out of recursion, and so it represents the sum of values from multiple branches of your recursion tree.

The first solution to look at would be to pass currentMax as an argument: this way it becomes a local variable that will not affect the caller's variable with the same name. See also the answer to your follow-up question further below.

But then we get to other problems:

This algorithm searches all possible paths that can be made. As the code challenge may pass you an array with up to one hundred thousand entries, you would try to visit 2¹⁰⁰⁰⁰⁰ states, which is practically impossible even if you keep your PC (or the fastest supercomputer) running for the rest of your lifetime.

You could prevent this exponential explosion by using memoization.

But then you'll bump into the limit of the call stack. The limit on the JS call stack may not support a depth of 100000. So then you should convert the algorithm to an iterative one:

Iterative algorithm

You could apply this logic:

Track the best result when we end at index and chose as last activity 0, 1 or 2: so we have three "bests".

When the index is increased, these bests can be updated as follows:

• Choosing activity 0: take points[0] and add the maximum of the previous bests we had for activity 1 and 2
• Similarly we can determine the best for the other activities at index index, and so we arrive at three updated bests, one for each activity.

Here is a spoiler implementation based on that approach:

maximumPoints(points, n) { let dp = points[0]; for (let index = 1; index < n; index++) { const [a, b, c] = points[index]; dp = [ a + Math.max(dp[1], dp[2]), b + Math.max(dp[0], dp[2]), c + Math.max(dp[0], dp[1]), ]; } return Math.max(...dp); }

Follow up question

When we make a local variable, maxPoint, shoudn't the next recursive call reset this variable to 0 again and again.

They each reset their own variable; the caller's variable with the same name is not affected by that initialisation.

The maxpoint variable is really local and is not affected by recursive calls. In your code that maxpoint gets a value that is returned by the recursive call, and so will be at least that value from that time onwards. In a next iteration it may get greater still. When return maxPoint is executed, it will represent the best value that could be combined from a recursive call and a current point's value.

And so we get this effect: when the recursion is unwinding, sums are made where each point with a greater index is represented. Ultimately the top-level caller will get a sum that is composed of 𝑛 values, each one coming from a distinct points entry.