LeetCode

本体使用动态规划来解决

1. 首先由于所有的房屋是首位相连的，所以意味着如果打劫了第一家就不能打劫最后一家；如果打劫最后一家就不能打劫第一家；所以我们就可以把问题分成两部分，只打劫第一家的最大金钱数 和 只打劫最后一家的最大金钱数
2. 然后我们就可以吧这个数组分成两个独立的数组， [0, nums.length -1) 和 [1, nums.length)
3. 再套用198题打家劫舍的解题思路即可

1. 首先我们定义dp数组：dp[i]表示打劫到i房子时的最大金钱数；
2. 然后找到状态转换方程：由于不能打劫相邻的房屋，所以可以得出要不然就打劫 i 和 i-2的房屋，要不就打劫i-1的房屋，判断哪一种得到的钱是最多的，即dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
3. 初始状态：dp[0]代表只打劫第一家则为nums[0]，dp[1]代表前两家打劫一家，要选择钱更多的打劫所以为Math.max(nums[0], nums[1]);

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[dp.length - 1];
    }
}

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        if (nums.length == 3) return Math.max(nums[0], Math.max(nums[1], nums[2]));

        int[] preNums = new int[nums.length - 1];
        int[] nextNums = new int[nums.length - 1];

        preNums = Arrays.copyOfRange(nums, 1, nums.length);
        nextNums = Arrays.copyOfRange(nums, 0, nums.length - 1);
        int p1 = getMaxMoney(preNums);
        int p2 = getMaxMoney(nextNums);
        return Math.max(p1, p2);
    }

    public int getMaxMoney(int[] nums) {
        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 - 1], dp[i - 2] + nums[i]);
        }
        return dp[dp.length - 1];
    }
}