raid homes and plunder houses!

subject

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 were 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 , Calculate if you don't touch the alarm , The maximum amount that can be stolen overnight .
Example ：

Code

class Solution {
    
    public int rob(int[] nums) {
    
        //dp[i]: It means the first one i Maximum amount of room theft 
        int len = nums.length;
        if(len == 1)  return nums[0];
        int[] dp = new int[len];
        // initialization 
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        // Traverse 
        for(int i = 2; i < len; i++){
    
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[len-1];
    }
}

213. raid homes and plunder houses II

subject

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 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 .
Example ：

Ideas

Consider the ring formation ！！！
Situation 1 ： Consider including the first element , No tail elements
Situation two ： Consider including tail elements , Does not contain the first element

Code

class Solution {
    
    public int rob(int[] nums) {
    
        int len = nums.length;
        if(len == 1)  return nums[0];
        return Math.max(robAction(nums,1,len),robAction(nums,0,len-1));
    }
    int robAction(int[] nums,int start,int end){
    
        int x = 0, y = 0, z = 0;
        for(int i = start; i < end; i++){
    
            //dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            y = z;
            z = Math.max(y,x + nums[i]);
            x = y;
        }
        return z;        
    }
}

337. raid homes and plunder houses III

subject

The thief found a new area to steal . There is only one entrance to the area , We call it root .

except root outside , Each house has and only has one “ Father “ The house is connected to it . After some reconnaissance , The clever thief realized that “ All the houses in this place are arranged like a binary tree ”. If Two directly connected houses were robbed the same night , The house will alarm automatically .
Given a binary tree root . return Without triggering the alarm , The maximum amount a thief can steal .
Example ：

Ideas

It must be After the sequence traversal , Because the next calculation is done through the return value of the recursive function
Grab the current node , Two children can't move , If you don't grab the current node , You can consider robbing children （ Notice what's going on here “ consider ”
1. Determine the parameters and return values of recursive functions
Require a node The money obtained by the two states of stealing and not stealing , Then the return value is a length of 2 Array of dp Array （dp table） And the meaning of subscripts ： Subscript to be 0 Record the maximum money obtained by not stealing the node , Subscript to be 1 Record steal The maximum money obtained by this node .
2. Determine termination conditions
If you encounter Blank nodes Words , Obviously , Stealing or not is 0, So go back to
3. Determine the traversal order
After the sequence traversal
4. Determine the logic of monolayer recursion
Steal the current node , Then the left and right children can't steal val1 = cur->val + left[0] + right[0];
If you don't steal the current node , Then the left and right children can steal , As for whether to steal or not, we must choose the biggest , therefore ：val2 = max(left[0], left[1]) + max(right[0], right[1]);

Code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public int rob(TreeNode root) {
    
       int[] res =  robAction(root);
       return Math.max(res[0],res[1]);
    }
    int[] robAction(TreeNode root){
    
        //dp[0] It means not stealing this node ,dp[1] It means stealing the node 
        int[] dp = new int[2];
        if(root == null){
    
            return dp;
        }
        // After the sequence traversal 
        int[] l = robAction(root.left);
        int[] r = robAction(root.right);

        dp[0] = Math.max(l[0],l[1]) + Math.max(r[0],r[1]);
        dp[1] = root.val + l[0]+r[0];
        return dp;

    }
}