preface

“This is the 24th day of my participation in the August More Text Challenge.

  1. 198. Robbery
  2. 213. Robbery II

198. Robbery

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

 

Example 1:

Input: [1,2,3,1] Output: 4 Explanation: Steal House # 1 (amount = 1), then steal House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4.

Analysis of ideas:

DP [I] represents the maximum amount of money that can be stolen when the ith room is grabbed

  1. Because if you rob room I, you can’t rob room I-1
  2. dp[i] =max( dp[i-2] + nums[i], dp[i-1) )

For I, it is only relevant to the selection of the first two rooms, so the DP array can be compressed into a loop of two variables

AC code:

    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int rob = i - 2> =0 ? dp[i - 2] + nums[i] : nums[i];
            dp[i] = Math.max(dp[i - 1], rob);
        }

        return dp[nums.length - 1];
    }
Copy the code

213. Robbery II

You are a professional thief, planning to rob the houses along the street, each with a certain amount of cash hidden inside. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with an interconnected security system, if two adjacent houses are broken into on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal tonight without setting off the alarm.

 

Example 1:

Input: nums = [2,3,2] Output: 3 Explanation: You cannot steal house 1 (amount = 2) and then house 3 (amount = 2) because they are adjacent. Example 2:

The first and last rooms can not be robbed at the same time, so there are only three cases

  1. The first room and the last room do not withdraw money
  2. Only take money from the first room, not the last room
  3. I only take money from the last room, not the first room

So if you adjust the solution to the first problem, you can adjust the snatch interval, length len

max(rob(0.. len -2), rob(1.. len-1))

AC code:

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

    public int rob(int[] nums, int start, int end) {

        if (start > end) {
            return 0;
        }
        int len = end - start + 1;
        int[] dp = new int[len];
        dp[0] = nums[start];

        for (int i = 1; i < len; i++) {
            int rob = i - 2> =0 ? dp[i - 2] + nums[i + start] : nums[i + start];
            dp[i] = Math.max(dp[i - 1], rob);
        }

        return dp[len - 1];
    }
Copy the code