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

代码随想录算法训练day39--动态规划之《打家劫舍系列》

news 来源：原创 2025/5/18 11:13:43

代码随想录算法训练

—day39

文章目录

代码随想录算法训练
前言
一、198.打家劫舍
二、213.打家劫舍II
三、337.打家劫舍 III
总结

前言

今天是算法训练的第39天，希望自己能够坚持下来！
今日任务依旧是动态规划，不过是打家劫舍系列：
● 198.打家劫舍
● 213.打家劫舍II
● 337.打家劫舍II

一、198.打家劫舍

题目链接
文章讲解
视频讲解

思路：

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
递推公式：对于房屋i，有偷和不偷两种选择。
①偷：就是考虑i-2个房屋最多金额+i房屋的金额（因为i-1相邻，不能偷），也就是
dp[i - 2] + nums[i]
②不偷：就是考虑i-1个房屋最多金额 dp[i - 1]
最后取两者最大值dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
初始化：因为需要i-2，i-1，所以初始化dp[0] = num[0] dp[1] = max[num[0], num[1]]
遍历顺序：从递推公式可知，从前往后遍历
举例推导dp数组：

代码如下：

class Solution {
public://dp[i]:考虑下标为i及i之前的所有房屋，能够偷到的最高金额为dp[i]//递推公式:dp[i] = max(dp[i-2] + nums[i], dp[i-1])//偷i：dp[i-2] + nums[i]  不偷：dp[i-1]  取两者最大值//初始化dp[0] = nums[0]   dp[1] = max(nums[0], nums[1])int rob(vector<int>& nums) {if (nums.size() == 0) return 0;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.打家劫舍是差不多的，唯一区别就是成环了。
分别考虑三种情况：
情况一：考虑不包含首尾元素
在这里插入图片描述
情况二：考虑包含首元素，不包含尾元素

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

实际上情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。
分别用198.打家劫舍逻辑求出情况二和情况三最大金额，最后取两者较大值。

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
递推公式：对于房屋i，有偷和不偷两种选择。
①偷：就是考虑i-2个房屋最多金额+i房屋的金额（因为i-1相邻，不能偷），也就是
dp[i - 2] + nums[i]
②不偷：就是考虑i-1个房屋最多金额 dp[i - 1]
最后取两者最大值dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
初始化：因为需要i-2，i-1，所以初始化dp[0] = num[0] dp[1] = max[num[0], num[1]]
遍历顺序：从递推公式可知，从前往后遍历

需要注意的是，去掉首或尾如果只剩下一个元素了，直接返回当前元素即可。

代码如下：

class Solution {
public://198.打家劫舍的逻辑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];}int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];//分别去掉首，尾来进行遍历，解决首尾相连的问题，最后取最大值int result1 = robRange(nums, 0, nums.size() - 2); //只考虑[0, nums.size() - 2]int result2 = robRange(nums, 1, nums.size() - 1); //只考虑[1, nums.size() - 1]return max(result1, result2);}
};

三、337.打家劫舍 III

题目链接
文章讲解
视频讲解

思路：
这道题需要在树形上做状态记录，可以用一个长度为2的数组，来记录偷和不偷的情况最大金额。

递归三部曲：
1.确定递归函数的参数和返回值：函数传入当前节点，返回长度为2的dp数组。

vector<int> robTree(TreeNode* cur){}

这里dp[0]记录不偷该节点的最大金额，dp[1]记录偷该节点的最大金额

2.确定终止条件：在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

if (cur == NULL) return vector<int>{0, 0};

也相当于dp数组的初始化
3.确定遍历顺序：首先明确的是使用后序遍历。因为要通过递归函数的返回值来做下一步计算。分别递归左节点和右节点，得到分别偷和不偷的最大金额。

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

4.确定单层递归的逻辑
①偷当前节点，那么左右节点就不能偷，val1 = cur->val + left[0] + right[0];
②不偷当前节点，左右节点都可以偷，但不一定偷，要看哪个最大，
val2 = max(left[0], left[1]) + max(right[0], right[1]);
左节点偷或者不偷最大值+右节点偷或者不偷最大值

5.举例推导dp数组
在这里插入图片描述
最后头结点就是取下标0 和下标1的最大值就是偷得的最大金钱。

代码如下：

/*** 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://定义长度为2的数组， 0：不偷，1：偷vector<int> robTree (TreeNode* node) {if (node == nullptr) return vector<int>{0,0};vector<int> left = robTree(node->left);vector<int> right = robTree(node->right);//偷当前节点,则左节点和右节点不能偷int result1 = node->val + left[0] + right[0]; //不偷当前节点，左右节点偷或不偷取最大值相加int result2 = max(left[0], left[1]) + max(right[0], right[1]);return vector<int> {result2, result1};}int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}
};

总结

打家劫舍：
1.dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
2.递推公式按照偷和不偷两种情况分析，
①偷：就是考虑i-2个房屋最多金额+i房屋的金额（因为i-1相邻，不能偷），也就是
dp[i - 2] + nums[i]
②不偷：就是考虑i-1个房屋最多金额 dp[i - 1]
最后取两者最大值dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
3.当题目有成环的条件时，可以分成去掉首，去掉尾两种情况去考虑，最后取最大值
4.在二叉树中使用动规方法，需要在递归函数中，将dp数组作为返回参数。

明天继续加油！