【LeeCode】213. 打家劫舍 II

【题目描述】

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

 https://leetcode.cn/problems/house-robber-ii/

【示例】

【代码】admin

思路： 同 【LeeCode】198. 打家劫舍

但这里的题目要求写的是  前后2个房间相邻, 本题是把1个数组拆分成了2个数组，取做大值

例如, 房间分别是 {1, 2, 3, 4} 则结果就是 Max（{1， 2， 3}， {2， 3， 4}）

package com.company;

import java.util.Arrays;

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        // 特殊场景, 如果只有1个, 则直接返回
        if (len == 1) return nums[0];

        int[] arr1 = Arrays.copyOfRange(nums, 0, len - 1);
        int[] arr2 = Arrays.copyOfRange(nums, 1, len);

        System.out.println( Math.max(check(arr1), check(arr2)));
        return Math.max(check(arr1), check(arr2));
    }

    public int check(int[] arr) {
        int len = arr.length;
        // dp[x] = y,表示前x个房间中获取的最大的金额是y
        int[] dp = new int[len + 1];
        // 初始化
        dp[0] = 0;
        dp[1] = arr[0];
        for (int i = 2; i <= len; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i - 1]);
        }
        return dp[len];
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().rob(new int[]  {2,3,2});  // 输出 3
        new Solution().rob(new int[] {1,2,3,1});  // 输出 4
        new Solution().rob(new int[] {1,2,3});  // 输出 3
    }
}