当前位置:网站首页>团灭 LeetCode 打家劫舍 问题

团灭 LeetCode 打家劫舍 问题

2020-11-09 22:18:43 谁在写西加加

 LeetCode 「打家劫舍」系列问题共有三道:

198.打家劫舍

213.打家劫舍II

337.打家劫舍III

 

House Robber I

int rob(vector<int>& nums);

建模:给定数组 nums中都是正整数,nums中相邻的数不能同时取,制定一种取数策略,

使得取到的nums中的数和最大,返回取到的数的最大和。

思路:题目很容易理解,而且动态规划的特征很明显。解决动态规划问题的关键就是找「状态」和「选择」。

1. 定义状态:定义dp[i] 表示 数组 nums[0:i]取数返回的最大和;

2. 状态转移: 根据数学归纳的方法, 求状态转移方程就是  假设 dp[0,1,2,...,i-1]都已知 求dp[i] 。

若 取 nums[i]  就不能取 nums[i-1],dp[i] = nums[i] + dp[i-2]  ;若不取 nums[i]  ,则 nums[i-1] 可以取

也可以不取,dp[i] = dp[i-1],dp[i] 取两种选择的最大值。最终的状态转移方程为:

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

状态转移方程中 有dp[i] ,dp[i-1]  ,dp[i-2],为了保证数组的下标从0开始,i 应从 2 开始,dp[0],dp[1],应该作为

base case 在状态转移之前处理好。因为只涉及到相邻 3 个状态,所以 可以将状态数组空间压缩,使用

两个变量 front ,before_front 记录状态。

代码如下:

         

 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

      这题和第一题 唯一的不同是nums由普通数组变成了环数组,即  nums[n-1 ] 和 nums[0] 也是相邻的,

在选择是否取  nums[n-1] 时,需要考虑到 nums[n-2] 和nums[0] 都是相邻的,选择nums 中的其他元素 和

上一题同样处理。代码如下:

 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         //根据是否 偷 nums[n-1] 分情况讨论,将问题转化为一般的 打家劫舍问题
 9         int res1 = rob_helper(nums,0,n-2);//不偷 nums[n-1]
10         int res2 = rob_helper(nums,1,n-3) + nums[n-1];//偷 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

     第一题的房子排列是 一个普通的数组,要求不能取相邻的房子内的钱。第二题的房子排列成一个环形数组,

首尾相接,要求不能取相邻的房子内的钱。第三题的房子分布在一颗二叉树上的节点上,要求不能取相邻的房子内的钱。

方法一:备忘录 + 递归 

思路分析:二叉树问题,显然可以用递归解决。根据题意,对二叉树的根节点:

1. 如果不取根节点的房子的钱,则作为根节点的相邻节点,根的左节点和根的右节点 都可以取 可以不取,递归地计算

左子树和右子树,然后相加就可以了。

2. 如果取根节点的房子的钱,则根的左节点和根的右节点 都不能取了,递归地计算根节点的左节点的左子树、根节点的

左节点的右子树、根节点的右节点的左子树、根节点的右节点的右子树,将 4 个递归计算得到的结果再加上 root->val 就是

取根节点的房子的钱 这种选择的结果。

3. 在1,2 两个结果中取最大值即得到最终的结果。

注:在递归计算的过程中,计算得到的子树的结果存到备忘录中,避免重复计算,提高效率。

代码如下:

      

 1 class Solution {
 2 private:
 3         unordered_map<TreeNode*,int> memo;//备忘录
 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 }

方法二: 更高效漂亮的递归

 1 int rob(TreeNode root) {
 2     int[] res = dp(root);
 3     return Math.max(res[0], res[1]);
 4 }
 5 
 6 /* 返回一个大小为 2 的数组 arr
 7 arr[0] 表示不抢 root 的话,得到的最大钱数
 8 arr[1] 表示抢 root 的话,得到的最大钱数 */
 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     // 抢,下家就不能抢了
15     int rob = root.val + left[0] + right[0];
16     // 不抢,下家可抢可不抢,取决于收益大小
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 }

 

版权声明
本文为[谁在写西加加]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/wangxf2019/p/13950234.html