LeetCode 198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.method
dp[i]: 从0到i能取到的最大值
考虑nums[i]，如果不偷，dp[i] = dp[i-1]
如果偷，dp[i] = dp[i-2] + nums[i]
所以递推公式dp[i] = max(dp[i-1], dp[i-2] + nums[i])
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]); // 取0和1之间的较大者
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}LeetCode 213. House Robber II
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.method
因为首尾相连，所以考虑三种情况
- 不考虑首尾
- 不考虑尾
- 不考虑首
因为情况2和情况3加一起就包含了情况1，所以就考虑两种情况
int robRange(vector<int>& nums, int start, int end) {
if (start == end) return nums[start];
vector<int> dp(nums.size());
dp[start] = nums[start];
dp[start + 1] = max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
int res1 = robRange(nums, 0, nums.size() - 2); // 情况2
int res2 = robRange(nums, 1, nums.size() - 1); // 情况3
return max(res1, res2);
}LeetCode 337. House Robber III
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Example 1:
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.Example 2:
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.method 1: 记忆化搜索
有两种情况：
- 不偷当前节点，考虑偷不偷左右节点
- 偷当前节点，接下来只能考虑孙子节点
两种情况取较大值，得到当前节点的结果后就记录下来
unordered_map<TreeNode*, int> hash;
int rob(TreeNode* root) {
if (!root) return 0;
if (hash[root]) return hash[root]; // 已经处理过就直接返回
int res1 = rob(root->left) + rob(root->right); // 情况1
int res2 = root->val; // 情况2
if (root->left) res2 += rob(root->left->left) + rob(root->left->right);
if (root->right) res2 += rob(root->right->left) + rob(root->right->right);
hash[root] = max(res1, res2); // 记录结果
return hash[root];
}method 2: 动态规划
res[1]表示不偷当前节点的结果res[2]表示偷当前节点的结果
pair<int, int> dfs(TreeNode* root) {
if (!root) return {0, 0};
auto [left1, left2] = dfs(root->left);
auto [right1, right2] = dfs(root->right);
int res1 = max(left1, left2) + max(right1, right2);
int res2 = root->val + left1 + right1;
return {res1, res2};
}
int rob(TreeNode* root) {
auto [res1, res2] = dfs(root);
return max(res1, res2);
}
