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.
1def rob(nums):
2 if not nums:
3 return 0
4 if len(nums) == 1:
5 return nums[0]
6
7 dp = [0] * len(nums)
8 dp[0] = nums[0]
9 dp[1] = max(nums[0], nums[1])
10
11 for i in range(2, len(nums)):
12 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
13
14 return dp[-1]
15
16nums = [2, 7, 9, 3, 1]
17print("Max amount that can be robbed:", rob(nums))Using a list 'dp' in Python where each element keeps the computed maximum value of money that can be robbed when considering the list of money up to that index. A choice is made at each house point to maximize profit.
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.
1#include <stdio.h>
2
3int rob(int* nums, int numsSize) {
4 if (numsSize == 0) return 0;
5 if (numsSize == 1) return nums[0];
6
7 int prev2 = nums[0];
8 int prev1 = (nums[1] > nums[0]) ? nums[1] : nums[0];
9 int current = prev1;
10
11 for (int i = 2; i < numsSize; ++i) {
12 current = (prev1 > prev2 + nums[i]) ? prev1 : prev2 + nums[i];
13 prev2 = prev1;
14 prev1 = current;
15 }
16
17 return current;
18}
19
20int main() {
21 int nums[] = {2, 7, 9, 3, 1};
22 int result = rob(nums, sizeof(nums)/sizeof(nums[0]));
23 printf("Max amount that can be robbed: %d\n", result);
24 return 0;
25}This C implementation contains no dp array but uses 'prev1' and 'prev2' variables to keep track of the maximum amounts robbed from the last house considered and the second last house, respectively. The current variable is updated each iteration.