198— raid homes and plunder houses （ One ）

Title Description

You are a professional thief , Plan to steal houses along the street . There is a certain amount of cash in every room , The only restriction on your theft is that adjacent houses are equipped with interconnected anti-theft systems , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm , The maximum amount that can be stolen overnight .

Their thinking

• Because adjacent rooms cannot be stolen continuously , So use interval theft ;
• You need to choose the one with high theft amount to steal , Finally, you can steal a relatively large amount ;
• In the k In front of a house , Faced with two situations ：
  • If you steal the first k A house , that k-1 A house cannot be stolen , At this time, the maximum amount should be k-2 The maximum amount of plus the current number k The wealth of a house ;
  • If you don't steal the first k A house , that At this time, the maximum amount should be k-1 The maximum amount of .
• So in front of every house , We have two options , The maximum amount we can get should be the larger of these two cases ;
• therefore State transition equation It can be written as ：

  

  Put a set of official schematic diagram of force buckle , It is convenient for us to understand the meaning of the question ：

I / O example

Code

You need to create two pointers to represent the maximum amount of the first two houses of the current house , Then dynamically update the two pointer variables , It can also be understood as dynamic interval method .

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        int sum = 0;
        int p = 0;// Record house  nums[i- 2]  Status of the maximum amount stolen ;
        int q = 0;// Record house  nums[i- 1]  Status of the maximum amount stolen ;
        for(int i = 0; i < len; i++ ){
            sum = Math.max(p+nums[i], q);// Record the current house  nums[i]  Status of the maximum amount stolen ;
            p = q;
            q = sum;
        }
        return q;
    }
}

213— raid homes and plunder houses （ Two ）

Title Description

You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are Make a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm device , The maximum amount you can steal tonight .

Their thinking

• In fact, the ideas of these two topics are similar , But this problem assumes that all houses are connected in a closed loop ;
• Then we can understand it as ： If you steal the head, you can't steal the tail , If you steal the tail, you can't steal the first ;
• So we can split the original circular array into two arrays , One is 0 ——n - 1, The other is 1—— n ;
• Then choose the solution of the problem with the greater result among the two schemes .

I / O example

Code

The code may be a little more streamlined ~

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1)return nums[0];
        int p1 = 0;
        int q1 = 0;
        for(int i = 0; i < nums.length-1; i++){
            int sum1 = Math.max(p1 + nums[i],q1);
            p1 = q1; 
            q1 = sum1;
        }
        int p2 = 0;
        int q2 = 0;
        for(int i = 1; i < nums.length; i++){
            int sum2 = Math.max(p2 + nums[i],q2);
            p2 = q2; 
            q2 = sum2;
        }
        return Math.max(q1,q2);
    }
}