House Robber - Java Solution

1. Introduction

This blog post tackles the "House Robber" problem, a classic example of dynamic programming. The challenge involves a scenario where a robber aims to maximize the loot from a series of houses lined up in a street. The constraint is that adjacent houses cannot be robbed, as this would alert the police.

Problem

Given an integer array nums, where nums[i] represents the amount of money in the ith house, the task is to determine the maximum amount of money that can be robbed without alerting the police. The condition is that adjacent houses cannot be robbed.

2. Solution Steps

1. Recognize that the problem can be solved using dynamic programming.

2. Use an array dp to store the maximum amount that can be robbed up to each house.

3. Iterate through the houses, and for each house, calculate the maximum loot by either robbing this house and adding the amount from two houses back or skipping this house and taking the amount from the previous house.

4. The maximum of these two choices will be the optimal solution at each step.

5. Return the maximum amount found at the last house.

3. Code Program

public class HouseRobber {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(rob(nums)); // Test the function
    }

    // Function to calculate the maximum amount of money that can be robbed
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.length - 1];
    }
}

Output:

4

Explanation:

1. rob: This function calculates the maximum amount of money that can be robbed from a series of houses, represented by the array nums.

2. It first handles edge cases where the array is empty or has only one house.

3. The function uses a dynamic programming array dp, where dp[i] represents the maximum amount that can be robbed up to the ith house.

4. For each house starting from the third one, the function calculates the maximum amount by either robbing the current house (and adding the amount from the house two steps back) or skipping it (and taking the amount from the previous house).

5. The final element in dp represents the maximum amount that can be robbed from all houses.

6. This approach ensures that the problem is solved optimally at each step, considering whether to rob each house based on the maximum loot possible up to that point.