198.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3). 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
分析:
1.对于单个房屋 i 来说, 偷到的最高金额是什么 ? 对于第 i 间房子来说, 可以选择偷第 i 间房子, 或者不偷第 i 间房子; 当前的房屋 i 的最大金额和 前面的某一个房屋 j 之间是否存在重叠子结构 ? 存在, 因为当前的状态可以从前面的状态中转移过来, 所以考虑用动态规划来找最高金额
2.定义 dp[i] 为从 0..i 间房子偷到的最大金额, 对于第 i 天 的最大金额, 可以从 2 种情况转移过来, 如果不偷, 就是 dp[i] = dp[i-1]; 如果偷, 就是 dp[i] = dp[i-2] + nums[i]
dp[i] = max(
dp[i-2] + nums[i], // 第 i 天偷
dp[i-1] // 第 i 天不偷
)
3.base 条件是什么? dp[0] 是第1天的情况下最大金额默认是按照偷算, dp[1] 是第2天的情况下最大金额只有 2 种情况, 第 1 天偷或者第 2 天偷; 后续的天数都可以用上面的状态转移得来;
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 0) {
return 0;
}
if (len == 1) {
return nums[0];
}
vector<int> dp(len);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < len; ++i) {
// 状态转移: 当天不偷, 或者当天偷
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[len - 1];
}
};
213.打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。示例 1：输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：输入：nums = [1,2,3] 输出：3
分析:
1.相比 198, 多了一个有环的情况, 但我们发现和之前相比唯一产生干扰的地方是偷最后一间就不能偷第0间, 偷第0间就不能偷最后一间
2.可以分开考虑是否偷第 0 间, dp 的范围是 0..size-2, 或者 1..size-1; 二者取最大的金额是答案
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) {
return nums[0];
}
if (n == 2) {
return max(nums[0], nums[1]);
}
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i <= n - 2; ++i) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
int res1 = dp[n-2];
dp[1] = nums[1];
dp[2] = max(nums[1], nums[2]);
for (int i = 3; i <= n - 1; ++i) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
int res2 = dp[n-1];
return max(res1, res2);
}
};
337.打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。示例 1: 输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
示例 2: 输入: root = [3,4,5,1,3,null,1] 输出: 9 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
分析:
1.以 root 作为节点, 有两种偷法, 偷当前根节点和不偷当前根节点
偷法1. 偷当前根节点: root->val + root->left->left->val + root->left->right->val + root->right->left->val + root->right->right->val:
偷法2. 不偷当前根节点: rob(root->left) + rob(root->right)
class Solution {
public:
int rob(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int money = root->val;
if (root->left != nullptr) {
money += rob(root->left->left) + rob(root->left->right);
}
if (root->right != nullptr) {
money += rob(root->right->left) + rob(root->right->right);
}
return max(money, rob(root->left) + rob(root->right));
}
};
代码报超时, 用备忘录优化一下, 备忘录记录每个根节点的 money
class Solution {
private:
unordered_map<TreeNode*, int> mem;
public:
int rob(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (mem.find(root) != mem.end()) {
return mem[root];
}
int money = root->val;
if (root->left != nullptr) {
money += rob(root->left->left) + rob(root->left->right);
}
if (root->right != nullptr) {
money += rob(root->right->left) + rob(root->right->right);
}
int res = max(money, rob(root->left) + rob(root->right));
mem[root] = res;
return res;
}
};
2560. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。示例 1：输入：nums = [2,3,5,9], k = 2 输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。示例 2：输入：nums = [2,7,9,3,1], k = 2 输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
分析:
1.二分搜索问题, 只不过搜索过程需要沿用基础的 dp
2.搜索的二分左边界
3.状态转移
如果搜索的mid 是大于窃取能力的, 那么就不能转移, dp[i] = dp[i-1]
如果搜索的mid 是满足窃取能力的, dp[i] = max(dp[i-1], dp[i-2] + 1)
4.判断条件是dp[n-1] >= k
class Solution {
public:
int minCapability(vector<int>& nums, int k) {
int n = nums.size();
if (n == 1) {
return nums[0];
}
int left = *min_element(nums.begin(), nums.end());
int right = *max_element(nums.begin(), nums.end());
int ans = right;
while (left < right) {
int mid = left + (right - left) / 2;
vector<int> dp(n, 0);
if (nums[0] <= mid) {
dp[0] = 1;
}
dp[1] = min(nums[0], nums[1]) <= mid ? 1: 0;
for (int i = 2; i < n; ++i) {
// 如果偷窃能力没法满足, 只能顺延dp[i-1]
if (nums[i] > mid) {
dp[i] = dp[i-1];
// 如果偷窃能力能满足, 那么直接状态转移;
} else {
dp[i] = max(dp[i-1], dp[i-2] + 1);
}
}
// 满足搜索数量>=k的算一次搜索完毕, 然后缩右边界`;
if (dp[n-1] >= k) {
ans = mid;
right = mid;
} else {
left = mid + 1;
}
}
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
