目录
题目链接: 198.打家劫舍
思路
代码
题目链接: 213.打家劫舍II
思路
代码
题目链接: 337.打家劫舍III
思路
代码
总结
题目链接:198.打家劫舍
思路
①dp数组,考虑下标i所能偷取的最大金币数为dp[i]
②递推公式,dp[i] = max(dp[i-2] + nums[i], dp[i-1]),当前房间只有偷和不偷两个选择,如果上上个房间已经偷了,则当前房间必须偷才能满足最大;如果上一个房间已经偷过了,则当前房间一定不能偷。所以取这两种状态中的最大值进行dp数组更新
③dp数组初始化,dp[0] = nums[0],只有一个房间时一定要偷;dp[1] = max(nums[0], nums[1]),到第二个房间时,选择两个中金币最多的一个
④遍历顺序,由递推公式可知,后面的状态都由前面推导而来,所以遍历从前往后
⑤推导dp数组
代码
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];
}
};
题目链接:213.打家劫舍II
思路
与198.打家劫舍不同的是加入了环,考虑环有三种情况:不考虑首尾;不考虑尾;不考虑首。用上一题的思路,该题的后两种情况是包含第一种的。
代码
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 1)
return nums[0];
// 不考虑尾
int result1 = robRange(nums, 0, nums.size() - 2);
// 不考虑首
int result2 = robRange(nums, 1, nums.size() - 1);
// 返回最大值
return max(result1, result2);
}
// 打家劫舍
int robRange(vector<int>& nums, int start, int end) {
if (end == start)
return nums[start];
vector<int> dp(nums.size(), 0);
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];
}
};
题目链接:337.打家劫舍III
思路
本题将数据结构换成了二叉树,首先要确定二叉树的遍历顺序,因为需要用递归的返回值做进一步的计算,所以必须是后序遍历。递归三部曲:
①确定函数类型和参数,参数为树的根节点,函数类型为int型的数组
②确定终止条件,当遍历到空节点时向上返回
③单层递归逻辑,每个节点都有偷或者不偷两个选择,因此这里定义dp数组,长度为2,分别表示偷和不偷时的最大金币数
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
// 两个状态,0表示不偷,1表示偷
vector<int> traversal(TreeNode* cur) {
// 终止条件
if (cur == NULL)
return vector<int>{0, 0}; // 空节点时偷与不偷都是0
// 后序遍历
vector<int> left = traversal(cur->left); // 左
vector<int> right = traversal(cur->right); // 右
// 中,单层递归逻辑
// 不偷当前节点,就可以偷孩子节点,选择最大的
int val0 = max(left[0], left[1]) + max(right[0], right[1]);
// 偷当前节点,就不能偷孩子节点
int val1 = cur->val + left[0] + right[0];
return {val0, val1};
}
int rob(TreeNode* root) {
vector<int> result = traversal(root);
return max(result[0], result[1]);
}
};
总结
①打家劫舍这种题的思路并不难,难点在于如何应用到不同的数据结构中
②数组的操作比较常规;环形数组分情况讨论,一开始不好想到
③二叉树中的动态规划,有两个关键点:一是二叉树结构数据的熟悉程度,主要是递归三部曲以及遍历顺序的选择;二是动态规划的熟练程度,主要是动规五部曲,与数组中的动态规划相比,dp数组的状态转移是逐层返回