I am trying to solve this problem I found on leetcode:
https://leetcode.com/problems/house-robber
We need to select a non adjacent combination with the largest sum and return it. Here is my attempt at solving this recursively
class Solution {
int[] arr;
int ans = 0;
private void helper(int i,boolean robprev,int curr){
/* i denotes index of array, robprev denotes whether previous house was selected,
curr denotes the current amount robbed */
ans = Math.max(ans,curr);
if(i>=arr.length)return;
if(!robprev){
helper(i+1,true,curr+arr[i]);
/* selected current house, move to next index, mark robprevious
as true and increment current amount */
}
helper(i+1,false,curr);
/* not selecting the current house, move next index,
current amount remains unchanged */
}
public int rob(int[] nums) {
arr = nums;
helper(0,false,0);
return ans;
}
}
As expected, I got a time limit exceeded error and my next thought was memoization, but I am unable to find where my algorithm is doing repeated word, as I am moving forward by one index each call.
Can someone suggest me how do I incorporate memoization in this approach ?
Yes, you're moving one index forward per call, but you're spawning two recursive calls, so that's a very high branching factor. Exponential O(2^n) to be precise.
The subproblems we're trying to memoize and avoid recomputation have to do with an index i. If we can compute the optimal robbery decisions for the subarray after i, then there's no need to revisit that.
The reason you may be struggling to memoize is that you're passing your result down the call stack in a parameter rather than up as a return value, making it difficult to determine which parameters constitute a key in the memoization lookup table. This table represents the solution to the subproblem starting at a particular index. An important rule of thumb for recursion, and especially for DP, is to pass data down and results up.
Additionally, robprev is unnecessary and frustrates memoization. You can simply skip an index when traversing when you're choosing not to rob a house. This makes your recursive calls look like i + 1 and i + 2 with respect to the indices.
Try this method header:
private int helper(int[] nums, int i, HashMap<Integer, Integer> memo);
First rewrite it naively expoentially with this header that returns an int, but ignore the memo parameter and make sure it works. Once you've ensured correctness, store each result before your return in the memo table and add a lookup to see if a parameter set is available before executing the recursive computation for that i.
If you're still stuck after that, see this answer which provides the solution in Python and should be easily translatable to Java. OP in that thread was also struggling to memoize House Robber because they were passing results down the call tree rather than up.
Using a bottom-up approach with a 2d array would be a good exercise once you have memoization. The array length on LeetCode is only 100 elements, but if it were 10k or so, a linear recursive algorithm will fail.