This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

Leetcode198: Raids

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

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.

Analysis of the problem

Method 1

To know the maximum amount to steal, you first need to analyze the stealing rules. Thieves may not steal from adjoining houses. Accordingly, it can be analyzed that the maximum amount of stealing to the current house is the maximum of the three: stealing to the previous house, stealing to the first two houses and stealing the current house, stealing to the first three houses and stealing the current house. Using the idea of dynamic programming, the state transition equation to obtain the maximum amount of theft is to maximize the three. Meanwhile, the amount stolen to a house is directly taken as dp array. From the perspective of logic and spatial optimization, it is only necessary to record the amount of theft in the two adjacent houses, and the spatial complexity can be optimized by repeated use of variables. N1 represents the first house, N2 represents the first two houses, and N3 represents the first three houses. The first three houses are treated with special treatment. So far, the problem analysis is solved.

public int rob(int[] nums) {
    if(nums.length == 0){
        return 0;
    }else if(nums.length == 1){
        return nums[0];
    }else if(nums.length == 2){
        return Math.max(nums[0],nums[1]);
    }else if(nums.length == 3){
        return Math.max(nums[0] + nums[2],nums[1]);
    }
    int n1 = Math.max(nums[2] + nums[0],nums[1]);
    int n2 = nums[1];
    int n3 = nums[0];
    for (int i = 3; i < nums.length; i++) {
        int max = Math.max(Math.max(n2+nums[i],n3+nums[i]),n1);
        n3 = n2;
        n2 = n1;
        n1 = max;
    }
    return n1;
}
Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (1)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.