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 <iostream>
2#include <vector>
3using namespace std;
4
5int rob(vector<int>& nums) {
6 if (nums.empty()) return 0;
7 if (nums.size() == 1) return nums[0];
8
9 vector<int> dp(nums.size(), 0);
10 dp[0] = nums[0];
11 dp[1] = max(nums[0], nums[1]);
12
13 for (int i = 2; i < nums.size(); ++i) {
14 dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
15 }
16
17 return dp.back();
18}
19
20int main() {
21 vector<int> nums = {2, 7, 9, 3, 1};
22 cout << "Max amount that can be robbed: " << rob(nums) << endl;
23 return 0;
24}Similar to the C implementation, we form a dp array in which each element at index 'i' holds the maximum sum we can achieve by considering houses up to index 'i', and choose between robbing or skipping house 'i'.
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.
1def rob(nums):
2 if not nums:
3 return 0
4 if len(nums) == 1:
5 return nums[0]
6
7 prev1, prev2 = 0, 0
8 for num in nums:
9 temp = prev1
10 prev1 = max(prev2 + num, prev1)
11 prev2 = temp
12 return prev1
13
14nums = [2, 7, 9, 3, 1]
15print("Max amount that can be robbed:", rob(nums))The optimized space Python solution abandons the use of a dp list in favor of tracking the last two maximum results on each iteration, consistent with the choices made of rob or not considering the current house.