This approach uses a dynamic programming table, where we maintain an array 'dp' such that dp[i] represents the maximum amount of money that can be robbed up to house i. We iterate through the list of houses and for each house, decide whether to rob it or skip it, based on the previous results stored in the dp table.
Time Complexity: O(n) - We iterate through all houses once.
Space Complexity: O(n) - We use an additional array 'dp' to store intermediate results.
1class Solution {
2 public int rob(int[] nums) {
3 if (nums.length == 0) return 0;
4 if (nums.length == 1) return nums[0];
5
6 int[] dp = new int[nums.length];
7 dp[0] = nums[0];
8 dp[1] = Math.max(nums[0], nums[1]);
9
10 for (int i = 2; i < nums.length; i++) {
11 dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
12 }
13 return dp[nums.length-1];
14 }
15
16 public static void main(String[] args) {
17 Solution sol = new Solution();
18 int[] nums = {2, 7, 9, 3, 1};
19 System.out.println("Max amount that can be robbed: " + sol.rob(nums));
20 }
21}Java implementation where an integer array 'dp' keeps track of the maximum amount of money that can be robbed considering all houses up to the ith index. The decision to rob or skip is based on maximizing the amount for each house.
This approach optimizes the space complexity by not using a separate array for storing results of subproblems. Instead, we use two variables to keep track of the maximum amount that can be robbed up to the last two houses considered. This eliminates the need for an auxiliary array and reduces space complexity to O(1).
Time Complexity: O(n) - Elements from the house array are each visited once.
Space Complexity: O(1) - Only a few extra variables are used for keeping track.
1class Solution {
2 public int rob(int[] nums) {
3 if (nums.length == 0) return 0;
4 if (nums.length == 1) return nums[0];
5
6 int prev1 = 0, prev2 = 0, current = 0;
7
8 for (int num : nums) {
9 int temp = current;
10 current = Math.max(prev1 + num, prev2);
11 prev1 = prev2;
12 prev2 = temp;
13 }
14 return current;
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] nums = {2, 7, 9, 3, 1};
20 System.out.println("Max amount that can be robbed: " + sol.rob(nums));
21 }
22}In this Java solution, prev1 and prev2 manage houses up to the current house being considered, replacing the function of a dp array with sequence variables and logic to determine inclusion.