-
Notifications
You must be signed in to change notification settings - Fork 3
/
House_Robber.cpp
69 lines (57 loc) · 1.39 KB
/
House_Robber.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// memoization
class Solution {
public:
int f(int i,vector<int>&nums,vector<int>&dp){
if(i==0)return nums[0];
if(i<0)return 0;
if(dp[i]!=-1)return dp[i];
int rob=f(i-2,nums,dp)+nums[i];
int nonRob=f(i-1,nums,dp)+0;
return dp[i]=max(rob,nonRob);
}
int rob(vector<int>& nums) {
int n=nums.size();
vector<int>dp(n,-1);
return f(n-1,nums,dp);
}
};
// Time complexity-->O(n) and
// space complexity-->O(n)for axuliry space + O(n) for dp array =O(2n) or O(n)
// Tabulation
class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
vector<int>dp(n,-1);
dp[0]=nums[0];
for(int i=1;i<n;i++){
int rob=nums[i];
if(i>1) rob+=dp[i-2];
int nonRob=dp[i-1];
dp[i]=max(rob,nonRob);
}
return dp[n-1];
}
};
// Time complexity-->O(n) and
// space complexity-->O(n) (dp array)
// Space Optimization
class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
int prev=nums[0];
int prev2=0;
for(int i=1;i<n;i++){
int rob=nums[i];
if(i>1) rob+=prev2;
int nonRob=prev;
int curr_i=max(rob,nonRob);
prev2=prev;
prev=curr_i;
}
return prev;
}
};
// Time complexity-->O(n) and
// space complexity-->O(1)