-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhouseRob2.java
More file actions
68 lines (58 loc) · 2.33 KB
/
houseRob2.java
File metadata and controls
68 lines (58 loc) · 2.33 KB
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
import java.util.Arrays;
class houseRob2 {
public static int rob(int[] nums) {
if (nums.length == 0 || nums == null) return 0;
if (nums.length == 1) return nums[0];
// get max loot of 1 - second to last
// another max of last to second
// max of those
// create arrays of skipLast and skipFirst
int[] skipLast = new int[nums.length-1];
int[] skipFirst = new int[nums.length-1];
for (int i = 0; i < nums.length - 1; i++) {
skipLast[i] = nums[i];
skipFirst[i] = nums[i+1];
}
System.out.println("skipLast: " + Arrays.toString(skipLast));
System.out.println("skipFirst: " + Arrays.toString(skipFirst));
// Get loot from both
int lootSkipLast = robHelper(skipLast);
int lootSkipFirst = robHelper(skipFirst);
return Math.max(lootSkipLast, lootSkipFirst);
}
private static int robHelper(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[nums.length - 1];
}
public static void main(String[] args) {
// int[] nums1 = {2, 3, 2};
// System.out.println(rob(nums1));
// System.out.println();
// int[] nums2 = {1, 2, 3, 1};
// System.out.println(rob(nums2));
// System.out.println();
int[] nums3 = {2, 7, 3, 1, 4, 2, 1, 8};
System.out.println(rob(nums3));
}
}
/*
Can't rob first and last houses
https://leetcode.com/problems/house-robber-ii/description/
You are a professional robber planning to rob houses along
a street. Each house has a certain amount of money stashed.
All houses at this place are arranged in a circle. That means
the first house is the neighbor of the last one. Meanwhile,
adjacent houses have a security system connected, and it will
automatically contact the police if two adjacent houses were
broken into on the same night.
Given an integer array nums representing the amount of money
of each house, return the maximum amount of money you can rob
tonight without alerting the police.
*/