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.
1#include <stdio.h>
2#include <string.h>
3
4int rob(int* nums, int numsSize) {
5 if (numsSize == 0) return 0;
6 if (numsSize == 1) return nums[0];
7
8 int dp[numsSize];
9 memset(dp, 0, sizeof(dp));
10
11 dp[0] = nums[0];
12 dp[1] = nums[1] > nums[0] ? nums[1] : nums[0];
13
14 for (int i = 2; i < numsSize; ++i) {
15 dp[i] = (dp[i-1] > dp[i-2] + nums[i]) ? dp[i-1] : dp[i-2] + nums[i];
16 }
17
18 return dp[numsSize-1];
19}
20
21int main() {
22 int nums[] = {2, 7, 9, 3, 1};
23 int result = rob(nums, sizeof(nums)/sizeof(nums[0]));
24 printf("Max amount that can be robbed: %d\n", result);
25 return 0;
26}This solution defines a 'dp' array where each entry at index 'i' stores the maximum money that can be robbed from the first 'i+1' houses. At each house, you choose the maximum value between not robbing the current house or robbing it and adding its value to the maximum of all the previous non-adjacent houses.
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 <iostream>
2#include <vector>
3using namespace std;
4
5int rob(vector<int>& nums) {
6 if (nums.size() == 0) return 0;
7 if (nums.size() == 1) return nums[0];
8
9 int prev1 = nums[0], prev2 = 0, current = nums[0];
10
11 for (size_t i = 1; i < nums.size(); ++i) {
12 current = max(prev1, prev2 + nums[i]);
13 prev2 = prev1;
14 prev1 = current;
15 }
16 return current;
17}
18
19int main() {
20 vector<int> nums = {2, 7, 9, 3, 1};
21 cout << "Max amount that can be robbed: " << rob(nums) << endl;
22 return 0;
23}This solution uses two variables instead of the dp array, storing only the necessary information to calculate the amount to be robbed using the rob-skip logic in C++. The maximum value of these calculations is returned.