How to use memoization in my code?

Question

I have a problem statement as follows: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money in each house, determine the maximum amount of money you can rob tonight without alerting the police.

I am coding it in Java. I am using Dynamic Programming to solve this problem and the code gives me the correct solution. However, the code is not efficient since I am using recursion and not using memoization to solve the problem. How do I use the concept of memoization into this code to make my code efficient? Here's my code:

class Solution {

    public int rob(int[] nums) {
        return robmax(nums,nums.length-1);    
    }

    public int robmax(int[] nums,int n) {
        int max = 0;
        if(nums.length==0) return 0;
        if(n==1) return Math.max(nums[0],nums[1]);
        if(n==0) return nums[0];
        else{
            max = Math.max(nums[n]+robmax(nums,n-2),robmax(nums,n-1));
        }
        return max;
    }
}

Also, what is the run time complexity of my algorithm.

Initialize an array memo of n values to -1 to denote nothing in the array. The first line in your function should check if memo[n] is < 0 and if so, do the work. The last line should return memo[n]. Then modify your function to store the computed result in memo[n]. As for your complexity, I believe your original form is O(phi^n) where phi=1.618... See a discussion on the Fibonacci series as to why. For the memoized form, try that one yourself. — MFisherKDX
– MFisherKDX, Commented Nov 21, 2017 at 20:51
What have you tried? I feel most questions asked these days are just peoples homework... — Wesley De Keirsmaeker
– Wesley De Keirsmaeker, Commented Nov 21, 2017 at 21:11

janos · Accepted Answer · 2017-11-21 20:44:34Z

1

You don't need memoization to solve this, or recursive calls. A dynamic programming solution will work nicely and much simpler. You can find the solution in a single pass over the elements. Consider this algorithm:

Initialize max to 0
For each house, the maximum you can rob is either of:
- the maximum value as of house[i-2] + the value of the current house
- the maximum value as of house[i-1]

That is, track the known maximum as of the previous house, and the previous-previous. by the time you reach the last house, you will have the accumulated maximum sum. Here's the outline, I hope I don't spoil the exercise:

public int rob(int[] nums) {
    int max = 0;
    int prev = 0;
    int prevprev = 0;
    for (int current : nums) {
        // TODO: 3 lines to solve the puzzle
    }
    return max;
}

answered Nov 21, 2017 at 20:44

janos

126k31 gold badges242 silver badges253 bronze badges

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

3 Comments

MFisherKDX Over a year ago

I agree. And I almost posted this. But this is not the OP's question.

user45437 Over a year ago

I wanted to use memoization. Your solution just uses dp. Anyway, Thanks

janos Over a year ago

@user45437 Fair enough. I was concerned that a memoization solution will not give a passing result due to its memory requirement (O(n) instead of the optimal O(1)). And somebody else already gave you a memoization strategy in a comment, so it won't be appropriate if I add that to my answer now. I understand that this is not what you were looking for, and that's fine.

Collectives™ on Stack Overflow

How to use memoization in my code?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related