LeetCode_c++: 打家劫舍一锅端

打家劫舍全家福系列

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

方法1. 动态规划，递归，备忘录，自顶向下

class Solution {
public:unordered_map <int,int> memo;int rob(vector<int>& nums) {        return dp(nums, 0);}int dp(vector<int>& nums, int index) {// end conditionif (index >= nums.size()) return 0;  // memo searchif(memo.count(index)) return memo[index];int res = max(nums[index] + dp(nums, index+2), dp(nums, index+1));// memo recordmemo[index] = res;return res;}
};

方法2. 动态规划，自底向上

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size()+2, 0);  //dp[i]定义为i开始能偷到的最高金额for(int i=nums.size()-1; i>=0; --i) {dp[i] = max(dp[i+1], nums[i]+dp[i+2]);}return dp[0];}
};

*由于结果只依赖最近的两个状态，还可以将空间复杂度降到O(1)

class Solution {
public:int rob(vector<int>& nums) {int dp1 = 0;int dp2 = 0;int dp = 0;for(int i=nums.size()-1; i>=0; --i) {dp = max(dp1, nums[i]+dp2);dp2 = dp1;dp1 = dp;}return dp;}
};

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

把上题code简单升级一下就可以，环形说白了就是要考虑第一家不偷，最后一家不偷这两种情况，还是用递归，这里没采用空间复杂度的降维，能到O(1)，有兴趣的可以自己试一下

class Solution {
public:unordered_map<string, int> memo;int rob(vector<int>& nums) {// base caseif (nums.size() == 1) return nums[0];return max(dp(nums, 0, nums.size()-2), dp(nums, 1, nums.size()-1));}int dp(vector<int>& nums, int start_index, int end_index) {// end conditionif (start_index > end_index) return 0;  // memo searchstring key = std::to_string(start_index) + ',' + std::to_string(end_index);if(memo.count(key)) return memo[key];int res = max(nums[start_index] + dp(nums, start_index+2, end_index), dp(nums, start_index+1, end_index));// memo recordmemo[key] = res;return res;}
};

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

class Solution {
public:unordered_map <TreeNode*, int> memo;int rob(TreeNode* root) {// bsae caseif (!root) return 0;  // memo searchif (memo.count(root)) return memo[root];int steal = root->val + (!root->left ? 0 : rob(root->left->left) + rob(root->left->right)) + (!root->right ? 0 : rob(root->right->left) + rob(root->right->right));int not_steal = rob(root->left) + rob(root->right);int res = max(steal, not_steal);// memo recordmemo[root] = res;return res;}
};