当前位置：首页 > news >正文

第四十七天 | 198.打家劫舍 213.打家劫舍|| 337.打家劫舍|||

news 来源：原创 2024/7/2 14:26:42

题目：198.打家劫舍

怎么确定当前的房间偷还是不偷呢？其实和前两个房间有关系的——动态规划

1.dp数组含义：考虑下标 i 和 i 之前的房间（dp[i] 不一定会偷第 i个房间）,所能偷的最大的金币

2.动态转移方程：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

两种情况：①偷第 i 房间，也就意味着一定不能头nums[i - 1]：dp[i - 2] + nums[i]

②不偷第 i 个房间，那么最大值来自dp[i - 1]：dp[i - 1]

3.初始化：递推公式的基础是dp[0] 和 dp[1]

dp[0] = nums[0]，dp[1] = max(dp[0]，dp[1])

紧贴公式来考虑怎样来初始化：当i = 0时，第一个房价是一定要偷的；当i = 1时，dp[1]应该为前两个房间所能偷的最大值，又因为两个房间不能一起偷，所以去前两个房间的最大值作为dp[1]。这样就叫紧贴dp含义来进行初始化

4.遍历顺序：从小到大，i 从2开始

5.打印dp

代码如下：

class Solution {
public:int rob(vector<int>& nums) {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.打家劫舍||
这道题和198.打家劫舍的区别就在于本题：最后一个房屋和第一个房屋紧挨着，所有房间围成一个圈。这样的话会带来什么影响呢？

思路：化环形为线型

在遇到环时可以如此考虑，展开呈线型

情况一：考虑不包含首尾元素
情况二：考虑包含首元素，不包含尾元素
情况三：考虑包含尾元素，不包含首元素

注意这里是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！对于情况三，取nums[1] 和 nums[3]就是最大的。

而情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。

代码如下：

有一些溢出判断是很值得注意的

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];int res1 = robRange(nums, 0, nums.size() - 2);int res2 = robRange(nums, 1, nums.size() - 1);return max(res1, res2);}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];}
};

题目：337.打家劫舍|||（值得理解）

打家劫舍|||在前两道题的基础上升级为树的问题，那么就会想到必然涉及到递归.

思路：

后序遍历树，从底向上，记录每一个节点偷和不偷的最优情况，依据左右孩子的状态，层层上推，然后将最优解集中在根节点上

1.1.dp数组的定义：二叉树结构应该怎么定义dp？怎样表示每个节点的状态？

每一层的dp只有两种可能——偷还是不偷。所以只有dp[0]（存放不偷当前节点所获得的最大金额）和dp[1]（存放偷当前节点所获得的最大金额）两种可能。

并且每一层的dp只来表示当前层这个金币的状态。

2.1递归函数的返回值：返回vector<int>，其实就是返回本层的dp数组。（那我可不可以只将两个情况当中金额较大的数值返回呢，后面不也要比较dp[0]和dp[1]求一个最优解么，为什么不直接将最优值返回呢？）

2.2/1.3递归函数终止条件/dp数组初始化：

当遇到空节点时，无论偷还是不偷都是0，所以就返回

vector<int> {0, 0}

1.4遍历顺序

后序遍历。因为要通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

// 下标0：不偷，下标1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右

2.4单层递归逻辑/动态转移方程：

不偷当前孩子：int val1 = max(left[0], left[1]) + max(right[0], right[1]);

偷当前孩子：int val2 = root -> val + left[0] + right[0];

最后将 {val1, val2}作为本层的dp数组返回给上一层

代码如下：

class Solution {
public:vector<int> robtree(TreeNode* root){if(root == nullptr) return{0, 0};vector<int> left = robtree(root->left);vector<int> right = robtree(root->right);int val1 = max(left[0], left[1]) + max(right[0], right[1]);   //不偷本层节点int val2 = root->val + left[0] + right[0];      //偷本层节点，偷了本层节点就不能偷它的左右孩子return {val1, val2};        //返回本层的dp数组}int rob(TreeNode* root) {if(root == nullptr) return NULL;vector<int> result = robtree(root);return max(result[0], result[1]);}
};