解答
方案一：动态规划
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length < 2) {
return nums[0];
}
if (nums.length < 3) {
return Math.max(nums[0], nums[1]);
}
int[] robValues = new int[nums.length];
robValues[0] = nums[0];
robValues[1] = Math.max(nums[0], nums[1]);
for (int i = 2, imax = nums.length; i < imax; ++i) {
robValues[i] = Math.max(nums[i] + robValues[i - 2], robValues[i - 1]);
}
return robValues[nums.length - 1];
}
}
方案二：递归
class Solution {
public int rob(int[] nums, int pos) {
if (pos < 0) {
return 0;
}
if (pos < 1) {
return nums[pos];
}
int value = Math.max(nums[pos] + rob(nums, pos - 2), rob(nums, pos - 1));
return value;
}
public int rob(int[] nums) {
return rob(nums, nums.length - 1);
}
}
要点
使用动态规划的方法，可以得出答案。
准备的用例，如下
@Before
public void before() {
t = new Solution();
}
@Test
public void test001() {
assertEquals(4, t.rob(new int[] {
1, 2, 3, 1 }));
}
@Test
public void test002() {
assertEquals(12, t.rob(new int[] {
2, 7, 9, 3, 1 }));
}
@Test
public void test003() {
assertEquals(2, t.rob(new int[] {
2 }));
}
@Test
public void test004() {
assertEquals(7, t.rob(new int[] {
2, 7 }));
}
@Test
public void test005() {
assertEquals(7, t.rob(new int[] {
7, 2 }));
}
