LeetCode第198题 – 打家劫舍

题目

解答

方案一：动态规划

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 }));
}