# The problem of looting by leetcode

2020-11-09 22:18:43

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,dp, 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 ：

``` 1 int rob(vector<int>& nums)
2     {
3         if(nums.empty())    return 0;
4         if(nums.size() == 1) return nums;
5         if(nums.size() == 2) return max(nums,nums);
6         int before_front = nums;
7         int front = max(nums,nums);
8         for(int i = 2;i < nums.size();++i)
9         {
10             int temp = front;
11             front = max(front,before_front + nums[i]);
12             before_front = temp;
13         }
14         return front;
15     }```

### 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 It's also adjacent ,

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

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

``` 1 int rob(vector<int>& nums)
2     {
3         const int n = nums.size();
4         //base case
5         if(n == 1) return nums;
6         if(n == 2) return max(nums,nums);
7         if(n == 3) return max(max(nums,nums),nums);
8         // According to whether or not   steal  nums[n-1]  Discussion by situation , Turn the problem into a general one   Home raiding
9         int res1 = rob_helper(nums,0,n-2);// Don't steal  nums[n-1]
10         int res2 = rob_helper(nums,1,n-3) + nums[n-1];// steal  nums[n-1]
11         return max(res1,res2);
12     }
13
14     int rob_helper(vector<int>& nums,int low,int high)
15     {
16         int len = high - low + 1;
17         if(len == 1) return nums[low];
18         if(len == 2) return max(nums[low],nums[high]);
19
20         int before_front = nums[low];
21         int front = max(nums[low],nums[low+1]);
22         for(int i =low + 2;i <= high;++i)
23         {
24             int temp = front;
25             front = max(front,before_front + nums[i]);
26             before_front = temp;
27         }
28         return front;
29     }```

### 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 ：

``` 1 class Solution {
2 private:
3         unordered_map<TreeNode*,int> memo;// Memorandum
4 public:
5     int rob(TreeNode* root)
6     {
7         if(!root)   return 0;
8         if(memo.count(root))    return memo[root];
9         int not_cheif_root = rob(root->left) + rob(root->right);
10         int left_res = root->left == NULL?0:
11                        rob(root->left->left)+rob(root->left->right);
12         int right_res = root->right == NULL?0:
13                         rob(root->right->left)+rob(root->right->right);
14         int cheif_root = left_res + right_res + root->val;
15         memo[root] = max(not_cheif_root,cheif_root);
16         return max(not_cheif_root,cheif_root);
17     }
18 }```

Method 2 ： More efficient and beautiful recursion

``` 1 int rob(TreeNode root) {
2     int[] res = dp(root);
3     return Math.max(res, res);
4 }
5
6 /*  Return a size of  2  Array of  arr
7 arr  It means not to rob  root  Words , The maximum amount of money you get
8 arr  It means to rob  root  Words , The maximum amount of money you get  */
9 int[] dp(TreeNode root) {
10     if (root == null)
11         return new int[]{0, 0};
12     int[] left = dp(root.left);
13     int[] right = dp(root.right);
14     //  rob , You can't rob me
15     int rob = root.val + left + right;
16     //  No robbing , You can rob but not rob , Depending on the size of the payoff
17     int not_rob = Math.max(left, left)
18                 + Math.max(right, right);
19
20     return new int[]{not_rob, rob};
21 }```