JZX轻语：简
LeetCode 198 & 213 - 打家劫舍I、II
发表于2024年10月07日
这两道题目是LeetCode上的经典动态规划题目，都是关于打家劫舍的问题。对于第一道题目，可以定义一个数组dp，其中dp[i]表示在前i个房子中能偷到的最大金额。对于第i个房子，有两种选择：偷或者不偷。如果偷第i个房子，那么第i - 1个房子就不能偷，因此最大金额为dp[i - 2] + nums[i]；如果不偷第i个房子，那么最大金额取决于前i - 1个房子的结果，即dp[i - 1]。因此，状态转移方程为dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。最后，返回dp[n - 1]和dp[n - 2]中的较大值即可。
而对于第二道题目，由于房子是环形的，因此可以分两种情况讨论：偷第一个房子和不偷第一个房子。对于第一种情况，dp[0] = nums[0]，第1到第n - 2个房子的偷法采用第一题的做法，而最后一个房子不能偷，即dp[n - 1] = dp[n - 2]；对于第二种情况，第一个房子不能偷，即dp[0] = 0，第1到第n - 1个房子的偷法采用第一题的做法，而最后一个房子可以偷，即dp[n - 1] = dp[n - 2]。最后，返回这两种情况的较大值即可。
打家劫舍I的做法：
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
for (int i = 1; i < nums.size(); ++i) {
nums[i] = max(nums[i - 1], (i > 1 ? nums[i - 2] : 0) + nums[i]);
}
return max(nums[nums.size() - 1], nums[nums.size() - 2]);
}
};打家劫舍II的做法：
class Solution {
public:
int solve(vector<int> nums, bool first_selected) {
// 如果`first_selected`为`true`，则第一个房子可以偷，但最后一个房子不能偷
// 否则，第一个房子不能偷，最后一个房子可以偷
// 其余的房子的偷法采用第一题的做法
if (!first_selected) nums[0] = 0;
if (nums.size() == 1) return nums[0];
for (int i = 1; i < nums.size(); ++i) {
if (i < nums.size() - 1 || !first_selected)
nums[i] = max(nums[i - 1], (i > 1 ? nums[i - 2] : 0) + nums[i]);
else // i == nums.size() - 1 && first_selected
nums[i] = nums[i - 1];
}
return max(nums[nums.size() - 1], nums[nums.size() - 2]);
}
int rob(vector<int>& nums) {
return max(solve(nums, true), solve(nums, false));
}
};