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.
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;
}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:
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).
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.