题目描述

题解

动态规划

这道题与上一道打家劫舍题的唯一不同点在于首尾两个房子不能同时考虑, 也就是如果偷窃了第一个房子就不能偷窃最后一个, 反之亦然.

所以可以将该数组分成两个子数组. 一个是nums[0: len-1], 一个是nums[1: len]

第一道打家劫舍题的思路为:

状态定义

使用一个一维数组dp[i]来表示第i天所能获得的最大金额.

状态转移方程

对每一天的选择进行分析, 要么抢要么不抢两种选择

如果抢了:

dp[i] = nums[i] + dp[i-2]

如果不抢:

dp[i] = dp[i-1]

初始化

dp[0] = 0, 表示第零天能够抢到的金额为0

public int rob(int[] nums) {
    int len = nums.length;
    if (len == 0) {
        return 0;
    }
    if (len == 1) {
        return nums[0];
    }

    return Math.max(helper(Arrays.copyOfRange(nums, 0, len - 1)),
                    helper(Arrays.copyOfRange(nums, 1, len)));
}

private int helper(int[] nums) {
    int[] dp = new int[nums.length + 1];
    dp[0] = 0;
    dp[1] = nums[0];
    for (int i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i-1], nums[i-1]+dp[i-2]);
    }
    return dp[nums.length];

}