代码随想录算法训练营第三十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

题目链接：198.打家劫舍

解题思路：动态规划

具体思路：

首先处理边界情况，若数组仅 1 个元素则直接返回该元素值，初始化长度与 nums 一致的 dp 数组 dp[i] 表示抢劫到第 i 间房屋时能获得的最大金额，dp[0] 设为 nums[0]，第一间房屋的金额，dp[1]设为 nums[0] 和 nums[1] 的最大值，前两间房屋选金额更大的那间，从第 3 间房屋开始遍历，通过状态转移公式 dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]) 更新最大金额，抢劫第 i 间则加上 dp[i – 2] 的金额，不抢劫第 i 间则取 dp[i – 1] 的金额，取两者最大值，最终返回 dp[nums.size() – 1]，即抢劫所有房屋能获得的最大金额。

具体代码：

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

时间复杂度：O（n）

空间复杂度：O（n）

题目链接：213.打家劫舍II

解题思路：动态规划

具体思路：

首先处理边界情况，若数组仅 1 个元素则直接返回该值，由于房屋环形排列，首尾房屋不能同时抢劫，因此将问题拆分为两个子问题，一是抢劫从第 0 间到倒数第 2 间的房屋不包含最后一间，二是抢劫从第 1 间到最后一间的房屋不包含第一间，定义 robrange 函数实现打家劫舍的动态规划逻辑，该函数内初始化dp数组，dp[i]表示抢劫到第 i 间房屋的最大金额，设置起始位置的边界值后，通过状态转移公式 dp[i] = max(dp[i – 2] + nums[i], dp[i – 1]) 遍历计算，最终取两个子问题的结果最大值，即为环形房屋能抢劫到的最大金额。

具体代码：

class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
return max(robrange(nums, 0 , nums.size() – 2), robrange(nums, 1 , nums.size() – 1));
}

int robrange(vector<int>& nums, int start, int end) {
if (end == start) 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 – 2] + nums[i], dp[i – 1]);
}
return dp[end];
}
};

时间复杂度：O（n）

空间复杂度：O（n）

题目链接：337.打家劫舍III

解题思路：动态规划 + 后序遍历

具体思路：

定义 robtree 函数递归处理每个节点，返回长度为 2 的数组，[0] 表示不抢劫当前节点时的最大金额，[1] 表示抢劫当前节点时的最大金额，递归终止条件为遇到空节点时返回{0, 0}，通过后序遍历先递归处理左右子节点，获取左右子节点的状态数组，状态转移时，抢劫当前节点的金额 val1 = 当前节点值 + 左子节点不抢的金额 + 右子节点不抢的金额，不抢劫当前节点的金额 val2 = 左子节点抢或不抢的最大值 + 右子节点抢或不抢的最大值，最终 rob 函数调用 robtree 处理根节点，返回根节点抢和不抢两种状态的最大值，即为整棵树能抢劫到的最大金额。

具体代码：

class Solution {
public:
int rob(TreeNode* root) {
vector<int> ans = robtree(root);
return max(ans[0], ans[1]);
}

vector<int> robtree(TreeNode * cur) {
if (cur == nullptr) return vector<int>{0, 0};
vector<int> left = robtree(cur->left);
vector<int> right = robtree(cur->right);
int val1 = cur->val + left[0] + right[0];
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
};

时间复杂度：O（n）

空间复杂度：O（logn）