0

I am new to dynamic programming and I am trying to understand the basics of recursion and memoization while trying to solve the Max sum of non adjacent elements - Problem. After reading some theory, one of the basic properties of a recursive function is it should have over lapping sub problems. For the naïve brute force approach to this problem, for my code below, I am having a hard time seeing overlapping problems.

  1. Is the reason I am not able to see overlapping sub problems because I don't have a recursive relation?
  2. Do I always have to have a recurrence relation in order to have sub problems, i.e., all recursive problems may/may not have sub problems if there is no recurrence relation
  3. How can I add memoization if 1 or 2 is holds and I just made a mistake in analysis?

public static int maxSubsetSum(int[] arr) {
        HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();
        return maxSumHelper(arr, 0, arr.length , 0, new ArrayList<Integer>(), cache);
    }
    public static int maxSumHelper(int[]arr, int start, int end, int sum, ArrayList<Integer>combo, HashMap<Integer, Integer> cache){
        
        /*
         * if(cache.containsKey(start)) { return; }
         */
        if(start>=end){
            for(int i  = 0; i <combo.size();i++ ) {
                System.out.print(combo.get(i));
            }
            System.out.println();
            return sum;
        }
        for(int i = start; i < arr.length; i++){
            sum+= arr[i];
            combo.add(arr[i]);
            int withMax  = maxSumHelper(arr, i + 2, end, sum, combo, cache);
            sum-=arr[i];
            combo.remove(combo.size() - 1);
            int withoutMax = maxSumHelper(arr, i+ 2, end, sum, combo, cache);
            //cache.put(i, Math.max(withMax, withoutMax));
            max = Math.max(max,Math.max(withMax, withoutMax));
        }
        return max;
    }

Improve this question
4
  • 1
    withoutMax = maxSumHelper(arr, i+ 2, end, sum, combo, cache) looks wrong to me. Shouldn't that be a +1? Commented Mar 28, 2021 at 12:24
  • no, because for every i, I want the neighbour 1 over and not adjacent Commented Mar 28, 2021 at 12:57
  • That's the case where you didn't take i though. Commented Mar 28, 2021 at 12:59
  • @DavidEisentat, you are right! Commented Mar 28, 2021 at 13:17

2 Answers 2

Reset to default
2

one of the basic properties of a recursive function is it should have over lapping sub problems

This is a condition for getting a benefit from dynamic programming, but is not a condition for a recursive function in general.

I am having a hard time seeing overlapping problems.

They are there. But first a correction: the second recursive call should pass i+1 as argument, not i+2. This is because it deals with the case where you do not include the value at i for the sum, and so it is allowed to include the value at i+1.

Now take this example input, and looking for a sum that is maximised:

{ 1, 2, 3, 2, 0, 3, 2, 1 }
                 ^
                 i=5

Let's focus on the call that gets as argument start=5: the most we can add to the current sum is 3 + 1 = 4. This fact is independent on what the value is of the sum argument, and so we could benefit from a cache that would tell us what the maximised additional value is at a given index start.

There are many paths that lead to this call with start=5. The path (combo) could include any of these values from the input before index 5:

  • 1, 3, 0
  • 1, 2
  • 2, 2
  • 2, 0
  • 3, 0
  • 2
  • 0
  • nothing

So if the first case drills down to the end and determines that for index 5 the greatest additional value is 4 (3+1), there is no need to do this search again for the other cases, and you can just do return sum + cache.get(start).

Side note

It is better practice to let the recursive function return that "additional" sum, and not pass it the sum-so-far as argument. Just add the value of the current selection (if any) to the greatest of the sums that come back from recursive calls and return that. This way it is also clearer how you can use memoization.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you for putting me on the right path yet again with a great detailed explanation.
I am struggling a bit with the note....though I think what you are saying is for a particular index calculate the max additional sum it can offer. However, how do I keep track of the total sum without passing in the sum as a parameter. Any further clarification is greatly appreciated.
The sum grows out of recursion, bottom up. You get two sums from the two recursive calls, keep the greatest of those two, add arr[i] to it, and return that to your own caller.
...ahhh i see that which is why passing in the current sum in my function leads to wrong values being cached and hence I simply cannot cache Math.max(withMax, withoutMax) for index i as it contains the total sum and not just the additional...hmmmmm.....
-1

  1. You should be able to see overlapping subproblems even though you haven't developed a recursive relation yet. try drawing a recursive tree for the problem and it should help you visualize the subproblems(nodes of the tree) and edges(the cost)

  2. No, you don't need a recursive relation to get a subproblem, having subproblems will help you get a recursive relation. recursive relation is how you formally represent relationship between subproblems

  3. To add memoization, write the recursive solution and cache the results of each recursive call.

if there's anything you disagree with, comment down below

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.