lt.198. raid homes and plunder houses

[ Case needs ]

[ Thought analysis ]

Robbing is dp Classic problem solving , The five parts of dynamic planning are analyzed as follows ：

1. determine dp The meaning of array and its subscript .

dp[i] : Consider Subscripts i( Include i) The houses within , The maximum amount that can be stolen is dp[i]

2. Determine the recurrence formula

decision dp[i] The key factor is The first i Steal the room or not ,

If you steal the first i room , that dp[i] = dp[i - 2] + nums[i], because dp Always get the current state from the previous state , If you want to steal i, So the last time I could only steal i - 2 Subscript house , use dp[i - 2] + nums[i] To get stolen dp[i] Amount obtained
If you don't steal the first i room , that dp[i] = dp[i - 1], That includes i - 1 The greatest value a room can steal
therefore , Recursive formula is to steal and not steal dp[i] Maximum value of : dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

3. dp How to initialize an array

From the recurrence formula, we can get , dp Originally from dp[0] and dp[1] Start initialization , because dp[2] = Math.max(dp[1], dp[0] + nums[2]);
So we need to initialize dp[0] and dp[1], From the meaning of the title , dp[0] It means stealing the subscript 0 House of , dp[0] = nums[0]
and , dp[1] You can choose to steal dp[0], Don't steal dp[1], Or not to steal dp[0], steal dp[1], therefore , dp[1] = Math.max(nums[0], nums[1]);

4. Determine the traversal order
   dp[i] It's based on dp[i - 2] and dp[i - 1] Derived from , So it must be traversal from front to back ！

5. Give an example to deduce dp Array
   

[ Code implementation ]

class Solution {
    
    public int rob(int[] nums) {
    
        //1.  determine dp[i],  Indicates that the subscript is i The maximum amount you can steal from your house dp[i]
        int len = nums.length;
        int[] dp = new int[len];
        //2.  The recursive formula 
        //  steal  dp[i] = dp[i - 2] + nums[i]
        // Don't steal  dp[i - 1] = dp[i - 1]
        // dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])
        

        //3.  initialization 
        // dp[0] = nums[0];
        // dp[1] = Math.max(nums[0], nums[1]);
        dp[0] = nums[0];
        if(len > 1)dp[1] = Math.max(nums[0], nums[1]);

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

        return dp[len - 1];
    }
}

lt.213. raid homes and plunder houses II

[ Case needs ]

[ Thought analysis ]

• In fact, it is to split the ring into two queues , One is from 0 To n-1, The other is from 1 To n, Then return the two largest results .
  

[ Code implementation ]

class Solution {
    
    public int rob(int[] nums) {
    
        int len = nums.length;
        if(len == 1)return nums[0];
        if(len == 2)return Math.max(nums[0], nums[1]);
        return Math.max(
                myRob(Arrays.copyOfRange(nums, 0, len - 1)),
                myRob(Arrays.copyOfRange(nums, 1, len)));
    }

    public int myRob(int[] nums) {
    
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        if(n > 1)dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
    
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }
}

lt.337. raid homes and plunder houses III

[ Case needs ]

[ Train of thought analysis 1 , Recurrence of violence ]

• Directly from root Nodes begin to recurse down ,

1. Each layer can choose root node , And then add root Nodes on the left subtree of the left child , And plus root Nodes on the right subtree of the right child ;
2. Or choose not root node , Directly from root The left child + root The right child node of starts to calculate .

[ Code implementation one ]

class Solution {
    
    public int rob(TreeNode root) {
    
        if(root == null)return 0;
        if(root.left == null && root.right == null)return root.val;

        // Steal the parent node , val1
        //  Then you need to skip root Direct left and right child nodes 
        int val1 = root.val;
        // hold val1 +  Subsequent recursive functions ,  This function is responsible for calculating root Left and right subtrees and root The left and right nodes on the subtree of the right child of 
        if(root.left != null)val1 += rob(root.left.left) + rob(root.left.right);
        if(root.right != null)val1 += rob(root.right.left) + rob(root.right.right);

        // Don't steal the parent node , val2
        int val2 = rob(root.left) + rob(root.right);

        return Math.max(val1, val2);
    }
}

Train of thought analysis II , Mnemonic recurrence

• So you can use a map Save the calculated results , In this way, if you have calculated your grandchildren , Then the results of grandchildren can be reused when calculating children .

Train of thought Analysis III , Dynamic programming