前言
打家劫舍系列
198. 打家劫舍
1_动态规划
返回最大金额
不能同时取相邻两个数
数组数据全部非负
①dp数组含义
dp[i]表示前i个数中按规则取出的最大总和
②递推公式
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
当前最优可以从两个状态推出（前提是前面已经为最优解）：
1° 前一个数未取：则当前数取了，则总和最大
2° 前一个数已取：比较不考虑当前数字的最大总和 （dp[i] ） 以及不考虑上一个数字的最大总和加上当前数字（dp[i-2]+nums[i]：因为当上一个数字未取时，才可以取当前数字）
③dp数组初始化
因为递推公式中用到了i-2项
所以遍历时要从dp数组的第2项开始遍历，防止数组越界
所以要初始化dp数组第2项前面的所有项dp[0]和dp[1]可以手推出来0&nums[0]
④遍历顺序
当前最优由已知最优推出，应正序遍历
完整代码：文章来源：https://www.toymoban.com/news/detail-773622.html
int rob(vector<int>& nums) {
// 定义dp数组&初始化为0
// dp数组含义：在前i个数中按规则选择后的最大和
vector<int> dp(nums.size() + 1, 0);
// 因为递推公式会用到i-2，为保证不越界，初始化到1，并从2开始遍历
// dp[0]没有可选的数字---0
dp[0] = 0;
// dp[1]选上唯一一个数则为最大---nums[0]
dp[1] = nums[0];
// 遍历dp数组
for (int i = 2; i < dp.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);
// 返回答案
return dp[nums.size()];
}
2_优化空间复杂度
由递推公式可以看出来，当前项只需要用到前两项就可以推出
所以：
不用将dp数组长度开为nums数组的长度
用两个变量记录前两项的值
在遍历时更新
// 两个变量记录
// dp[i-2]
int ppre = 0;
// dp[i-1]
int pre = nums[0];
// dp[i]---初始化为nums[0]，当nums长度为1时范围首项
int cur = nums[0];
// 遍历nums数组
for (int i = 2; i <= nums.size();i++) {
cur = max(pre, ppre + nums[i-1]);
ppre = pre;
pre = cur;
}
// 返回答案
return cur;
213. 打家劫舍 II
1_动态规划
在打家劫舍Ⅰ的基础上加上了条件：
当第一间房子被偷过时，最后一间房子就不能偷
只有第一间房子，没被偷过时，最后一间房子才能偷
分（含头不含尾&含尾不含头）两段区间分别计算各自的最大值
动规五部曲和打家劫舍Ⅰ大致相同
需要注意：
①
int rob(vector<int>& nums) {
// nums数组长度为1时返回第一项
if (nums.size() == 1)
return nums[0];
// 定义dp数组
vector<int> dp(nums.size());
// 包含首索引---------------------
// 初始化0，1项
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i < dp.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
int m1 = dp[dp.size() - 1];
// 包含尾索引----------------------
// 初始化1项为2项（间接删除首索引）
dp[1] = nums[1];
for (int i = 2; i < dp.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
return max(m1, dp[dp.size() - 1]);
}
2_优化空间复杂度
int rob(vector<int>& nums) {
// 变量记录法
if (nums.size() == 1)
return nums[0];
// 含头不含尾----------------------
// dp[i-2]
int ppre = 0;
// dp[i-1]
int pre = nums[0];
// dp[i]
int cur1 = nums[0];
// 遍历nums数组
for (int i = 2; i < nums.size(); i++) {
cur1 = max(pre, ppre + nums[i - 1]);
ppre = pre;
pre = cur1;
}
// 含尾不含头
ppre = 0;
pre = nums[1];
int cur2 = nums[1];
for (int i = 3; i <= nums.size(); i++) {
cur2 = max(pre, ppre + nums[i - 1]);
ppre = pre;
pre = cur2;
}
// 返回两个区间里的较大者
return max(cur1, cur2);
}
337. 打家劫舍 III
0_复习树
因为跟树有关，我贴一个遍历方法出来：
递归法遍历树适用于各种
树节点结构体定义：
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) {}
};
根节点的构造和函数遍历函数调用：
int main() {
// [3,2,3,null,3,null,1]
TreeNode* root = new TreeNode(3, new TreeNode(2, nullptr, new TreeNode(3)), new TreeNode(3, nullptr, new TreeNode(1)));
postTraval(root);
return 0;
}
递归法的后序遍历
void postTraval(TreeNode* root) {
if (root == nullptr)
return;
// 左右中
if (root->left != nullptr)
postTraval(root->left);
if (root->right != nullptr)
postTraval(root->right);
cout << root->val << " ";
}
迭代法的后续遍历：
// 后序遍历_迭代版
void postTraval(TreeNode* root) {
/*
栈
先存入后访问
空指针标记
取节点时，判断是否为空指针
空指针：取出的是需要访问的节点
非空指针：加上空指针标记，便于后续取出访问
*/
// 数组做栈，存放遍历节点
TreeNode* stack[30] = { 0 };
// 栈顶指针
int top = -1;
// 预先存入根节点
stack[++top] = root;
// 迭代父节点---当栈不为空时，还有节点尚未遍历
while (top != -1) {
// 取出节点
TreeNode* cur = stack[top--];
if (cur != nullptr) {
// 存入节点---后序遍历（左右中）---栈的后入先出---（中右左）
// 存入当前节点时，需要加入标记---先入节点在入空指针
stack[++top] = cur;
stack[++top] = nullptr;
// 存左子节点
if (cur->right != nullptr)
stack[++top] = cur->right;
// 存右子节点
if (cur->left != nullptr)
stack[++top] = cur->left;
}
else {
// 进行访问---因为取出的是空指针，下一个栈顶才是要访问的节点
cur = stack[top--];
cout << cur->val << " ";
}
}
}
1_动态规划
本题里第一次涉及到树状dp
树状dp和数组dp只是数据结构不同
原理都是在遍历数据时进行状态转移
注意状态转移的方向
当选择后序遍历树时，因为是先进入左右子节点，所以当前状态才能从子状态中推出
①dp值含义
考虑当前节点及其所有子节点后，得到的最大值
②递推公式
选择两种情况中的最大值
1° 选择当前节点，递归进入孙子节点
val1=当前节点值+孙子节点的最大值2° 不选择当前节点，递归进入子节点
val2=左右子节点的最大值
// 偷当前节点---递归进入孙子节点
int val1 = root->val;
// 加入判断，避免操作空指针
if (root->left != nullptr)
val1 += rob(root->left->left) + rob(root->left->right);
if (root->right != nullptr)
val1 += rob(root->right->left) + rob(root->right->right);
// 不偷当前节点---递归进入子节点
int val2 = rob(root->left) + rob(root->right);
③因为子状态直接由各个节点值可以直接得出，所以不用初始化
④遍历顺序
选择后序遍历树
因为是先进入左右子节点，所以当前状态才能从子状态中推出
完整代码:
int rob(TreeNode* root) {
// 当传入节点为空时，返回0
if (root == nullptr)
return 0;
// 传入节点非空且无子节点时，返回当前节点值
if (root->left == nullptr && root->right == nullptr)
return root->val;
// 偷当前节点---递归进入孙子节点
int val1 = root->val;
// 加入判断，避免操作空指针
if (root->left != nullptr)
val1 += rob(root->left->left) + rob(root->left->right);
if (root->right != nullptr)
val1 += rob(root->right->left) + rob(root->right->right);
// 不偷当前节点---递归进入子节点
int val2 = rob(root->left) + rob(root->right);
// 在两种情况中返回较大值
return max(val1, val2);
}
2_记忆化搜索（备忘录）
提交会发现有测试用例超时，因为存在大量重复计算
例如：在不考虑当前节点时，进入的左右子节点可能已经通过之前的孙子节点计算过结果
所以可以通过设置一个数据结构来记录每一个节点的计算结果
数据结构的选择
本题中我们要选择一个能够存储树节点，并且能够通过树节点查询到其计算结果的数据结构
自然会想到使用map（通过键查询值）因为通过递归遍历树，所以不能选择在某一层建立map，应该开全局map
而平时是数组，仅需通过索引查询，用数组做备忘录就行
完整代码：
unordered_map<TreeNode*, int> visit;
int rob(TreeNode* root) {
// 当传入节点为空时，返回0
if (root == nullptr)
return 0;
// 传入节点非空且无子节点时，返回当前节点值
if (root->left == nullptr && root->right == nullptr)
return root->val;
// 在选择偷法前判断是否已经存在计算结果
if (visit.find(root) != visit.end())
return visit[root];
// ②find函数返回迭代器，通过second获取值
// return visit.find(root)->second;
// 偷当前节点---递归进入孙子节点
int val1 = root->val;
// 加入判断，避免操作空指针
if (root->left != nullptr)
val1 += rob(root->left->left) + rob(root->left->right);
if (root->right != nullptr)
val1 += rob(root->right->left) + rob(root->right->right);
// 不偷当前节点---递归进入子节点
int val2 = rob(root->left) + rob(root->right);
// 返回前存入结果
visit[root]=max(val1,val2);
// 插入键值对
// visit.insert(pair<TreeNode*,int>(root,max(val1,val2);
// 在两种情况中返回较大值
return max(val1, val2);
}
总结
打家劫舍的dp递推公式比较容易找到
难的是边界情况判断
以及跟树结合时需要使用备忘录文章来源地址https://www.toymoban.com/news/detail-773622.html
到了这里，关于动态规划_打家劫舍（Ⅰ~Ⅲ）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
