LeetCode 198. Looting & dynamic planning

Subject requirements

Link to the original title ：198. raid homes and plunder houses

The questions are as follows ：

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 .

Examples are as follows ：

Example 1：
Input ：[1,2,3,1]
Output ：4
explain ： Steal 1 House No ( amount of money = 1) , And then steal 3 House No ( amount of money = 3).
Maximum amount stolen = 1 + 3 = 4 .
Example 2：
Input ：[2,7,9,3,1]
Output ：12
explain ： Steal 1 House No ( amount of money = 2), Steal 3 House No ( amount of money = 9), Then steal 5 House No ( amount of money = 1).
Maximum amount stolen = 2 + 9 + 1 = 12 .

solution ： Dynamic programming

Ideas

Observation topic requirements , Easy to know n A house , You can choose to steal or not

• If you steal n A house , Then according to the requirements of the topic, you can't steal the n-1 A house , The final total amount of theft is the former n-2 The maximum amount of a house is the same as that of n The sum of the amount of each house .
• If you don't steal n A house , Then the total amount of theft is the former n-1 The maximum amount of a house .

A large problem depends on the solution of its subproblem , It is obvious that dynamic programming can be used to solve .

For the first n The decision to steal a house or not , What needs to be compared is the former n-1 The maximum amount of a room and the previous n-2 The maximum amount of a house + The first n Which house has the largest amount .

Use dp[i] Before presentation i The maximum amount of money stolen from a house , We can get the following equation of state transition ：
dp[i] = max(dp[i - 1, dp[i - 2] + nums[i])

According to the habitual thinking of dynamic planning , You might think of using a length equal to nums[] Array of dp[] Array for state representation , The spatial complexity of doing this is O(n),n Is the length of the original array , But by looking at the problem, we can find that , Each bottom-up traversal actually uses only dp[i - 2] and dp[i - 1], The rest of the space will no longer be used , So this can be optimized , Only two fixed extra spaces can be used to meet the demand , The space complexity is optimized to O(1) Level .

complete AC Code

class Solution {
    
    public int rob(int[] nums) {
    
    	// Boundary condition judgment 
        if(nums.length == 1)return nums[0];
        // dp[0] Forever means  nums[ Current house  - 2] The optimal solution of time 
        // dp[1] Forever means  nums[ Current house  - 1] The optimal solution of time 
        int[] dp = new int[2];
        //  initialization 
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i = 2; i < nums.length; i++){
    
            int temp = dp[1];
            dp[1] = Math.max(dp[0] + nums[i], dp[1]);
            dp[0] = temp;
        }
        return dp[1];
    }
}

Complexity analysis

Time complexity ：O(n),n by nums The length of the array .
Spatial complexity ：O(1), Just using extra variables at a fixed constant level .