The problem of looting by leetcode

 LeetCode 「 raid homes and plunder houses 」 There are three questions in this series :

198. raid homes and plunder houses

213. raid homes and plunder houses II

337. raid homes and plunder houses III

 

House Robber I

int rob(vector<int>& nums);

modeling ： Given array nums All of them are positive integers ,nums The adjacent numbers in cannot be taken at the same time , Develop a retrieval strategy ,

So that it gets nums The number in and the maximum of , Returns the maximum sum of the retrieved number .

Ideas ： The title is easy to understand , And the characteristics of dynamic programming are obvious . The key to solve the problem of dynamic programming is to find 「 state 」 and 「 choice 」.

1. Define the State ： Definition dp[i] Express Array nums[0:i] The maximum sum returned by fetching ;

2. State shift ： According to the method of mathematical induction , To solve the state transition equation is   hypothesis dp[0,1,2,...,i-1] All known seek dp[i] .

if take nums[i]  You can't take nums[i-1],dp[i] = nums[i] + dp[i-2]  ; If you don't take nums[i]  , be nums[i-1] Can take

You may not take ,dp[i] = dp[i-1],dp[i] Take the maximum of the two choices . The final state transition equation is ：

    dp[i] = max(dp[i-1],dp[i-2]+nums[i])

In the state transition equation Yes dp[i] ,dp[i-1]  ,dp[i-2], To ensure that the subscript of the array is from 0 Start ,i comply with 2 Start ,dp[0],dp[1], Should be as

base case Deal with it before the state transitions . Because it's only about neighbors 3 Status , therefore State array space can be compressed , Use

Two variables front ,before_front Record status .

The code is as follows ：

         

int rob(vector<int>& nums)
    {
        if(nums.empty())    return 0;
        if(nums.size() == 1) return nums[0];
        if(nums.size() == 2) return max(nums[0],nums[1]);
        int before_front = nums[0];
        int front = max(nums[0],nums[1]);
        for(int i = 2;i < nums.size();++i)
        {
            int temp = front;
            front = max(front,before_front + nums[i]);
            before_front = temp;
        }
        return front;
    }

 

House Robber II

      This and the first question The only difference is nums From an ordinary array to a ring array , namely   nums[n-1 ] and nums[0] It's also adjacent ,

In choosing whether to take   nums[n-1] when , Need to take into account nums[n-2] and nums[0] It's all adjacent , choice nums Other elements in and

The last question is also dealt with . The code is as follows ：

int rob(vector<int>& nums)
    {
        const int n = nums.size(); 
        //base case 
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0],nums[1]);
        if(n == 3) return max(max(nums[0],nums[1]),nums[2]);
        // According to whether or not   steal  nums[n-1]  Discussion by situation , Turn the problem into a general one   Home raiding 
        int res1 = rob_helper(nums,0,n-2);// Don't steal  nums[n-1]
        int res2 = rob_helper(nums,1,n-3) + nums[n-1];// steal  nums[n-1]
        return max(res1,res2);
    }
     
    int rob_helper(vector<int>& nums,int low,int high)
    {
        int len = high - low + 1;
        if(len == 1) return nums[low];
        if(len == 2) return max(nums[low],nums[high]);

        int before_front = nums[low];
        int front = max(nums[low],nums[low+1]);
        for(int i =low + 2;i <= high;++i)
        {
            int temp = front;
            front = max(front,before_front + nums[i]);
            before_front = temp;
        }
        return front;
    }

 

House Robber III

      What is the arrangement of the houses in question 1 A normal array , Ask not to take money from neighboring houses . The houses in question 2 are arranged in a circular array ,

Head to tail , Ask not to take money from neighboring houses . The houses in question 3 are distributed on the nodes of a binary tree , Ask not to take money from neighboring houses .

Method 1 ： Memorandum + recursive  

Thought analysis ： Binary tree problem , Obviously, it can be solved recursively . According to the meaning , For the root node of a binary tree ：

1. If you don't take the money from the root node's house , As the adjacent nodes of the root node , The left node of the root and the right node of the root You can take Can not take , Calculate recursively

Left subtree and right subtree , And then add it up .

2. If you take the money from the house of the root node , Then the left node of the root and the right node of the root You can't take it , Recursively calculates the left subtree of the left node of the root node 、 The root node of the

The right subtree of the left node 、 The left subtree of the right node of the root node 、 The right subtree of the right node of the root node , take 4 The result of recursive calculation plus root->val Namely

Take the money from the house of the root node The result of this choice is .

3. stay 1,2 Take the maximum of the two results to get the final result .

notes ： In the process of recursive computation , The result of the subtree is saved in the memo , Avoid double counting , Increase of efficiency .

The code is as follows ：

      

class Solution {
private:
        unordered_map<TreeNode*,int> memo;// Memorandum 
public:
    int rob(TreeNode* root) 
    {
        if(!root)   return 0;
        if(memo.count(root))    return memo[root];
        int not_cheif_root = rob(root->left) + rob(root->right);
        int left_res = root->left == NULL?0:
                       rob(root->left->left)+rob(root->left->right);
        int right_res = root->right == NULL?0:
                        rob(root->right->left)+rob(root->right->right);
        int cheif_root = left_res + right_res + root->val;
        memo[root] = max(not_cheif_root,cheif_root);
        return max(not_cheif_root,cheif_root);
    }
}

Method 2 ： More efficient and beautiful recursion

int rob(TreeNode root) {
    int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/*  Return a size of  2  Array of  arr
arr[0]  It means not to rob  root  Words , The maximum amount of money you get 
arr[1]  It means to rob  root  Words , The maximum amount of money you get  */
int[] dp(TreeNode root) {
    if (root == null)
        return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    //  rob , You can't rob me 
    int rob = root.val + left[0] + right[0];
    //  No robbing , You can rob but not rob , Depending on the size of the payoff 
    int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);
    
    return new int[]{not_rob, rob};
}