当前位置:网站首页>The problem of looting by leetcode

The problem of looting by leetcode

2020-11-09 22:18:43 Who's writing about Sica

 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 :

         

 1 int rob(vector<int>& nums)
 2     {
 3         if(nums.empty())    return 0;
 4         if(nums.size() == 1) return nums[0];
 5         if(nums.size() == 2) return max(nums[0],nums[1]);
 6         int before_front = nums[0];
 7         int front = max(nums[0],nums[1]);
 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[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 :

 1 int rob(vector<int>& nums)
 2     {
 3         const int n = nums.size(); 
 4         //base case 
 5         if(n == 1) return nums[0];
 6         if(n == 2) return max(nums[0],nums[1]);
 7         if(n == 3) return max(max(nums[0],nums[1]),nums[2]);
 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[0], res[1]);
 4 }
 5 
 6 /*  Return a size of  2  Array of  arr
 7 arr[0]  It means not to rob  root  Words , The maximum amount of money you get 
 8 arr[1]  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[0] + right[0];
16     //  No robbing , You can rob but not rob , Depending on the size of the payoff 
17     int not_rob = Math.max(left[0], left[1])
18                 + Math.max(right[0], right[1]);
19     
20     return new int[]{not_rob, rob};
21 }

 

版权声明
本文为[Who's writing about Sica]所创,转载请带上原文链接,感谢