动态规划_打家劫舍（Ⅰ~Ⅲ）

文章目录

• 前言
• [198. 打家劫舍](https://leetcode.cn/problems/house-robber/description/)
• • 1_动态规划
  • 2_优化空间复杂度
• [213. 打家劫舍 II](https://leetcode.cn/problems/house-robber-ii/description/)
• • 1_动态规划
  • 2_优化空间复杂度
• [337. 打家劫舍 III](https://leetcode.cn/problems/house-robber-iii/description/)
• • 0_复习树
  • 1_动态规划
  • 2_记忆化搜索（备忘录）
• 总结

前言

打家劫舍系列

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]

④遍历顺序

当前最优由已知最优推出，应正序遍历

完整代码：

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递推公式比较容易找到
难的是边界情况判断
以及跟树结合时需要使用备忘录