0
\$\begingroup\$

The problem states that you have to rob the maximum money stashed in the houses but you cannot rob two adjacent houses. array[i] denotes the money in the (i)th house. I got the following code submitted but Is there a more optimised aprroach. I saw a very small solution on the YouTube Channel 'NeetCode' but couldn't understand the solution.(https://youtu.be/73r3KWiEvyk). Below two test scenarios:

Example 1:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

package com.company;
import java.util.Arrays;

public class RobTheMax {
    static int Rob(int[] nums,int[] dp) {
        Arrays.fill(dp,-1);
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int val = rob(i,nums,dp);
            if (val > max) {
                max= val;
            }
        }
        return max;

    }
    static int rob(int indexToBegin,int[] nums,int[] storage) {
        int big_val = 0;
        int nums_val = nums[indexToBegin];
        int storage_value = storage[indexToBegin];
        if (storage_value != -1) {
            return storage_value;
        }

        if (indexToBegin + 2 >= nums.length) {
            return nums_val;
        } else {
            for (int i = indexToBegin + 2; i < nums.length; i++) {
                int val = rob(i,nums,storage);
                if (val > big_val) {
                    big_val = val;
                }
            }
            storage[indexToBegin] = big_val + nums_val;
            return big_val + nums_val;
        }
    }
    public static void main(String[] args) {
        int[] nums = {2,1,1,2};
        int[] dp = new int[nums.length];
        System.out.println("max robbery is " + Rob(nums,dp));
    }
}

Link to the original problem is https://leetcode.com/problems/house-robber/

\$\endgroup\$
3
  • \$\begingroup\$ Hello, I added the two test scenarios included in the link to the description of the problem for a better understanding of the task. \$\endgroup\$ Sep 25 '21 at 5:45
  • \$\begingroup\$ Copying your code to the leetcode site ends with a compilation error. Have you run it just locally and not on the site? \$\endgroup\$ Sep 25 '21 at 17:51
  • \$\begingroup\$ I confirm that this code works, just not as copy-pasted verbatim on leetcode. With cosmetic adaptation the solution passes on leetcode. \$\endgroup\$
    – janos
    Oct 14 '21 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.