目录
1. 打家劫舍1(线性数组)(LeetCode198)
题目描述：https://leetcode.cn/problems/house-robber/description/
- 题目简述：每间房内都藏有一定的现金(非负整数数组)，问一夜之内能够偷窃到的最高金额？
- 房间造型：线性数组
- 偷窃规则：相邻的房间不能同时偷窃
- 问题分析：当前房屋偷与不偷 取决于 前一个房屋和前两个房屋是否被偷了。可见，当前状态和前面状态会有一种依赖关系，因此可以使用动态规划来求解。
解法1：动态规划（二维dp数组）
解题思路：动态规划五部曲
- Step1：确定dp数组(一维)/dp表格(二维)、下标的含义
- dp[i][0]：第i个房间不被偷，一夜之内能够偷窃到的最高金额为dp[i][0]
- dp[i][1]：第i个房间被偷，一夜之内能够偷窃到的最高金额为dp[i][1]
- 每一个房间使用两个状态来表示
- Step2：确定递推公式
- dp[i][0] = max(dp[i-1][0], dp[i-1][1]) 第i个房间不被偷 → 第i-1个房间可以不被偷，也可以被偷
- dp[i][1] = dp[i-1][0] + nums[i] 第i个房间被偷 → 第i-1个房间一定不能被偷
- Step3：初始化dp数组
- 从递推公式可以看出，i是由i-1推导而来，因此需要初始化第一个元素
- dp[0][0]：第0个房间不被偷，一夜之内能够偷窃到的最高金额为0
- dp[0][1]：第0个房间被偷，一夜之内能够偷窃到的最高金额为nums[0]
- Step4：确定遍历顺序
- 从递推公式可以看出，i是由i-1推导而来，因此需要从前向后遍历
- Step5：打印dp数组（调试）
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int rob(vector<int>& nums)
{
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
// Step3：初始化dp数组
vector<vector<int>> dp(nums.size(), vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = nums[0];
// Step4：确定遍历顺序
for (int i = 1; i < nums.size(); i++)
{
// Step2：确定递推公式
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); // 不被偷
dp[i][1] = dp[i - 1][0] + nums[i]; // 被偷
}
return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
}
};
int main()
{
//vector<int> nums{ 1,2,3,1 }; // 4
vector<int> nums{ 2,7,9,3,1 }; // 12
Solution s;
int ans = s.rob(nums);
cout << ans << endl;
system("pause");
return 0;
}复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
解法2：动态规划（一维dp数组）
解题思路：
- Step1：确定dp数组(一维)/dp表格(二维)、下标的含义
- dp[i]：考虑[0,i]以内的房屋，一夜之内能够偷窃到的最高金额为dp[i]
- 注意：此处仅仅是考虑第i个房间，并不一定偷窃第i个房间
- Step2：确定递推公式
- dp[i] 可以由以下两个方向推导而来
- 偷第i个房间：dp[i-2] + nums[i] 此时应该考虑i-2及其之前的房间，该区间内的所有房间都有被偷和不被偷的可能（i-1不能考虑）
- 由于相邻房间不能同时偷窃 且 偷窃第i个房间，因此第i-1个房间一定不能偷窃
- 考虑[0,i-2]以内的房屋，一夜之内能够偷窃到的最高金额为dp[i-2] 加上 偷窃第i房间的钱
- 不偷第i个房间：dp[i-1] 此时应该考虑i-1及其之前的房间，该区间内的所有房间都有被偷和不被偷的可能
- 若不偷第i个房间，则第i-1个房间可以被偷，也可以不被偷
- 考虑[0,i-1]以内的房屋，一夜之内能够偷窃到的最高金额为dp[i-1]
- dp[i] = max(dp[i-2] + nums[i], dp[i-1])
- Step3：初始化dp数组
- 从递推公式可以看出，i是由i-2和i-1推导而来，因此需要初始化前两个元素
- dp[0]：仅考虑第0个房屋，一夜之内能够偷窃到的最高金额 → 偷窃第0个房间的金额
- dp[1]：仅考虑第0个和第1个房屋，一夜之内能够偷窃到的最高金额 → 由于相邻房间不能同时偷窃，因此两者只能选其一进行偷窃，因此最高金额为两者的最大值
- Step4：确定遍历顺序
- 从递推公式可以看出，i是由i-2和i-1推导而来，因此需要从前向后遍历
- Step5：打印dp数组（调试）
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
public:
int rob(vector<int>& nums)
{
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
// Step3：初始化dp数组
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// Step4：确定遍历顺序
for (int i = 2; i < nums.size(); i++)
{
// Step2：确定递推公式
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
int main()
{
//vector<int> nums{ 1,2,3,1 }; // 4
vector<int> nums{ 2,7,9,3,1 }; // 12
Solution s;
int ans = s.rob(nums);
cout << ans << endl;
system("pause");
return 0;
}复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
解法3：动态规划（一维dp数组优化）
解题思路：利用"状态压缩"进行优化 → 由于当前数值dp[i]仅依赖于前面两个数值dp[i-1]和dp[i-2]，因此只需要维护两个数值
class Solution
{
public:
int rob(vector<int>& nums)
{
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
// Step3：初始化dp数组
vector<int> dp(2);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
// Step4：确定遍历顺序
for (int i = 2; i < nums.size(); i++)
{
// Step2：确定递推公式
int dpi = max(dp[1], dp[0] + nums[i]);
dp[0] = dp[1];
dp[1] = dpi;
}
return dp[1];
}
};
int main()
{
//vector<int> nums{ 1,2,3,1 }; // 4
vector<int> nums{ 2,7,9,3,1 }; // 12
Solution s;
int ans = s.rob(nums);
cout << ans << endl;
system("pause");
return 0;
}复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2. 打家劫舍2(环形数组)(LeetCode213)
题目描述：https://leetcode.cn/problems/house-robber-ii/description/
题目简述：每间房内都藏有一定的现金(非负整数数组)，问一夜之内能够偷窃到的最高金额？
- 房间造型：环形数组，首尾两个房间为相邻房间
- 偷窃规则：相邻的房间不能同时偷窃
解题思路：针对首尾房间是否被偷，划分为以下几种情况，每种情况均可以使用"打家劫舍1"的代码求解
- 首房间和尾房间为相邻房间，因此不能同时被偷（必须限定其中一个不被偷）
- Case1：首房间不被偷，尾房间不做限定 → 考虑[1, nums.size()-1]以内的房屋，一夜之内能够偷窃到的最高金额
- Case2：尾房间不被偷，首房间不做限定 → 考虑[0, nums.size()-2]以内的房屋，一夜之内能够偷窃到的最高金额
#include <iostream>
using namespace std;
#include <vector>
class Solution
{
private:
// 该函数的代码与"打家劫舍1"完全相同
int robRange(vector<int>& nums)
{
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
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];
}
public:
int rob(vector<int>& nums)
{
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
// Case1：首房间不被偷，尾房间不做限定 → 考虑[1, nums.size()-1]以内的房屋，一夜之内能够偷窃到的最高金额
vector<int> vec1(nums.begin() + 1, nums.end());
int result1 = robRange(vec1);
// Case2：尾房间不被偷，首房间不做限定 → 考虑[0, nums.size()-2]以内的房屋，一夜之内能够偷窃到的最高金额
vector<int> vec2(nums.begin(), nums.end() - 1);
int result2 = robRange(vec2);
return max(result1, result2);
}
};
int main()
{
vector<int> nums{ 2,3,2 }; // 3
//vector<int> nums{ 1,2,3,1 }; // 4
Solution s;
int ans = s.rob(nums);
cout << ans << endl;
system("pause");
return 0;
}小结：环形问题不利于思考，可以将环形展开为线性结构，单独考虑首尾元素是否选取，分情况讨论
3. 打家劫舍3(二叉树)(LeetCode337)
题目描述：https://leetcode.cn/problems/house-robber-iii/description/
题目简述：每间房内都藏有一定的现金(非负整数数组)，问一夜之内能够偷窃到的最高金额？
- 房间造型：二叉树
- 偷窃规则：相邻的房间不能同时偷窃
#include <iostream>
using namespace std;
#include <vector>
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
{
private:
// Step1：确定递归函数的参数和返回值
// 返回值：长度为2的数组
// 下标0：该节点的房间不被偷窃，能够盗取的最高金额
// 下标1：该节点的房间被偷窃，能够盗取的最高金额
vector<int> traversal(TreeNode* root)
{
// Step2：终止条件（初始化dp数组）
// 对于空节点，无论偷还是不偷都是0
if (root == NULL) return vector<int>{ 0,0 };
// Step3：确定单层递归的逻辑（确定递推公式，确定遍历顺序 → 后序遍历）
vector<int> dp_left = traversal(root->left); // 左：递归左节点，得到左节点不被偷时所得到的最高金额dp_left[0]、左节点被偷时所得到的最高金额dp_left[1]
vector<int> dp_right = traversal(root->right); // 右：递归右节点，得到右节点不被偷时所得到的最高金额dp_right[0]、右节点被偷时所得到的最高金额dp_right[1]
vector<int> dp(2); // 中
// 当前节点不被偷：左右孩子被偷和不被偷均有可能
dp[0] = max(dp_left[0], dp_left[1]) + max(dp_right[0], dp_right[1]);
// 当前节点被偷：左右孩子不可能被偷，只可能是不被偷
dp[1] = dp_left[0] + dp_right[0] + root->val;
return vector<int>{dp[0], dp[1]}; // 返回当前节点的状态：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}
}
public:
int rob(TreeNode* root)
{
vector<int> result = traversal(root);
return max(result[0], result[1]);
}
};
int main()
{
// 7
//TreeNode* node1 = new TreeNode(3);
//TreeNode* node2 = new TreeNode(2);
//TreeNode* node3 = new TreeNode(3);
//TreeNode* node4 = new TreeNode(3);
//TreeNode* node5 = new TreeNode(1);
//node1->left = node2;
//node1->right = node3;
//node2->right = node4;
//node3->right = node5;
// 9
TreeNode* node1 = new TreeNode(3);
TreeNode* node2 = new TreeNode(4);
TreeNode* node3 = new TreeNode(5);
TreeNode* node4 = new TreeNode(1);
TreeNode* node5 = new TreeNode(3);
TreeNode* node6 = new TreeNode(1);
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->right = node6;
Solution s;
int ans = s.rob(node1);
cout << ans << endl;
system("pause");
return 0;
}