198. House raiding

1、 Title Description

 2、 Topic analysis

        This topic is 【 Dynamic programming 】 Classic topics , Previous pair 【 The problem of buying stocks 】【 Home raiding 】 Special analysis has been carried out , Thematic analysis will summarize and compare topics of the same type , It is more comprehensive than this single topic . I suggest you read what I wrote before , Blog posts on such topics , The corresponding links are as follows ：

        Algorithm sharing series No.7--( Interview practical problems in large factories ) Stock trading series & Home raiding

Therefore, this kind of problem is mainly to find recursive equations . The recursive idea is as follows ：

  According to the above recursive logic , Use auxiliary space dp The code implementation is as follows ：

class Solution {
    public int rob(int[] nums) {
        // The initial conditions 
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        
        // Dynamic programming , Auxiliary space dp
        int[] dp = new int[n];
        // To initialize 
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i = 2; i < n; i++){
          // Dynamic programming transfer equation 
          dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[n-1];
    }
}

Complexity analysis

Time complexity ：O(n), among n  It's array length . Just traverse the array once .

Spatial complexity ：O(n). Use auxiliary space dp Array , Record the temporary results of each element .

        Space optimization based on the above , Because of the discovery , The numerical , Just follow 【 First two rooms 】 The amount of the house , Therefore, there is no need for special use dp Auxiliary space for recording , It can be changed into a variable , In this way, the space complexity is reduced from the original array O(n) Reduce to a finite number of variable elements , The space complexity is reduced to O(1).

here ,【 Optimize space complexity 】 Let's write it as follows ：

class Solution {
    public int rob(int[] nums) {
        // The initial conditions 
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];

        int one = nums[0];
        int second = Math.max(nums[0],nums[1]);
        for(int i =2; i< n; i++){
            // Rolling calculation 
            int temp = second;
            second = Math.max(one+nums[i], second);
            one = temp;
        }
        return second;
   }
}

Complexity analysis

Time complexity ：O(n), among n  It's array length . Just traverse the array once .

Spatial complexity ：O(1). Use scrolling arrays , You can only store the maximum total amount of the first two houses , Instead of storing the results of the entire array , So the complexity of space is O(1).