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

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

 

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
输出：0

 

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
Related Topics
  • 数组
  • 动态规划

  • 👍 778
  • 👎 0

    • LeetCode刷题【198】打家劫舍的进阶题，其实倒也不是太进阶，原本的单条的数据变成了环，需要额外判断处理首位的情况。

    相关分析情况见代码行间注释。

    class Solution {
    public int rob(int[] nums) {
        if (nums.length==0)return 0;
        if (nums.length==1)return nums[0];
        int[][] dp = new int[nums.length][4];
        //两种情况，如果第一个房子不偷，那么最后一个房子可偷可不偷，取最大值
        //如果第一个房子偷，第二个房子只能不偷，最后个房子只能不偷取最大值
        //把单组数组4个下标分组
        // 0,1 为第一个房子不偷的情况下，0为当前房子偷，1位当前房子不偷
        // 2,3 为第一个房子偷的情况下，2为当前房子偷，3为当前房子不偷
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = nums[0];
        dp[0][3] = nums[0];
        dp[1][0] = nums[1];
        dp[1][1] = 0;
        dp[1][2] = nums[0];
        dp[1][3] = nums[0];
//        System.out.println(Arrays.toString(dp[0]));
//        System.out.println(Arrays.toString(dp[1]));
        int i = 2;
        for (; i < nums.length; i++) {
            dp[i][0] = dp[i-1][1] + nums[i];
            dp[i][1] = Math.max( dp[i-1][0] , dp[i-1][1] );
            dp[i][2] = dp[i-1][3] + nums[i];
            dp[i][3] = Math.max( dp[i-1][2] , dp[i-1][3] );
//            System.out.println(Arrays.toString(dp[i]));
        }
        return Math.max(dp[--i][3],Math.max(dp[i][0],dp[i][1]));
    }
}

    也可以用dp[n][2]的数组跑两次其实，不过我就图个省事一次遍历完成，就用了长度4的数组处理。