[Vssue]0213.打家劫舍II.md

[youngyangyang04]

https://www.programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html

[Du1in9]

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

    int money1 = robRange(nums, 0, nums.length - 2);
    int money2 = robRange(nums, 1, nums.length - 1);
    return Math.max(money1, money2);
}

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

// 例: nums = [1,6,1,9,1]
=> robRange(nums, 0, 3): dp = [1,6,0,0,0]
    i = 2: dp[2] = max(6, 1+1) = 6 (不偷), dp = [1,6,6,0,0]
    i = 3: dp[3] = max(6, 6+9) = 15 (偷), dp = [1,6,6,15,0]
=> robRange(nums, 1, 4): dp = [0,6,6,0,0]
    i = 3: dp[3] = max(6, 6+9) = 15 (偷), dp = [0,6,6,15,0]
    i = 4: dp[4] = max(15, 6+1) = 15 (不偷), dp = [0,6,6,15,15]