Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Naive Thinking: First thought was to use DP. The logic is as follows:
opt[i] // the maximum amount of money one rob without alerting the police.
// base case
opt[0] = 0
opt[1] = num[0]
// iteration
opt[i] = max(opt[i-1], opt[i-2]+num[i-1])
public class Solution {
public int rob(int[] num) {
if(num == null || num.length == 0) return 0;
int opt[] = new int[num.length+1];
// base case
opt[0] = 0;
opt[1] = num[0];
// iteration
for(int i = 2;i <= num.length;i++)
opt[i] = Math.max(opt[i-1], opt[i-2] + num[i-1]);
return opt[num.length];
}
}
From the structure of the code. It is easy to see the O(N) space could be constrained to O(1).
public class Solution {
public int rob(int[] num) {
if(num == null || num.length == 0) return 0;
// base case
int pre = 0;
int cur = num[0];
// iteration
for(int i = 2;i <= num.length;i++){
int temp = cur;
cur = Math.max(cur, pre + num[i-1]);
pre = temp;
}
return cur;
}
}
No comments:
Post a Comment