#198.
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下
，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1)
，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
思路：
解决动态规划问题就是找「状态」和「选择」
假设你就是这个小偷，从左到右走过这一排房子，在每间房子前都有两种「选择」：偷或者不偷。
如果你偷了这间房子，那么你肯定不能偷相邻的下一间房子，只能从下下间房子开始重复这样的选择。
如果你不偷这间房子，那么你就可以走到下一间房子前，继续做选择。
当你走过了最后一间房子后，你就没有房子偷了，偷到的钱为0（base
case）。
在两个选择中，每次选择更大的结果，最后得到的就是最多能偷到的钱
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
return dp(nums, 0);
}
int dp(vector<int>& nums, int i){
if(i >= nums.size()) return 0;
int res = max(dp(nums, i + 1),dp(nums, i + 2) + nums[i]);
return res;
}
};
|
明确了状态转移，就可以发现对于同一个
i位置，是存在重叠子问题的，可以用备忘录进行优化，避免多次递归浪费时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> memo;
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
memo.resize(nums.size(), -1);
return dp(nums, 0);
}
int dp(vector<int>& nums, int i){
if(i >= nums.size()) return 0;
if(memo[i] != -1) return memo[i];
int res = max(dp(nums, i + 1),dp(nums, i + 2) + nums[i]);
memo[i] = res;
return res;
}
};
|
这是自顶向下的动态规划，我们也可以改成自底向上：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
vector<int> dp(n + 2, 0);
dp[n] = 0;
for(int i = n - 1; i >= 0; i--){
dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]);
}
return dp[0];
}
};
|
我们又发现状态转移只和dp[i]最近的两个状态有关，所以可以进一步优化，将空间复杂度降低到
O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
int dp_i_1 = 0, dp_i_2 = 0;
int dp_i = 0;
for(int i = n - 1; i >= 0; i--){
dp_i = max(dp_i_1, dp_i_2 + nums[i]);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
};
|
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈
，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统,，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下
，今晚能够偷窃到的最高金额。
示例：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1
号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）,
因为他们是相邻的。
思路：
环形方案：首尾不能同时偷，有三种不同情况
1，都不偷
2，只偷首个房子
3，只偷尾房子
取最大结果即可
我们可以只考虑情况2和情况3，因为这两种情况对于房子的选择余地比情况一大，因为房子里的钱都是正数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
if(n == 1) return nums[0];
return max(dp(nums, 0, n - 2), dp(nums, 1, n - 1));
}
int dp(vector<int>& nums, int start, int end){
if(start >= end + 1) return 0;
int res = max(dp(nums, start + 1, end), dp(nums, start + 2, end) + nums[start]);
return res;
}
};
|
有重叠子问题，借用备忘录进行优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<vector<int> > memo;
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
if(n == 1) return nums[0];
memo.resize(n, vector<int>(n, -1));
return max(dp(nums, 0, n - 2), dp(nums, 1, n - 1));
}
int dp(vector<int>& nums, int start, int end){
if(start >= end + 1) return 0;
if(memo[start][end] != -1) return memo[start][end];
int res = max(dp(nums, start + 1, end), dp(nums, start + 2, end) + nums[start]);
memo[start][end] = res;
return res;
}
};
|
我们又发现状态转移只和dp[i][j]最近的两个状态有关，所以可以进一步优化，将空间复杂度降低到
O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
int robRange(vector<int>& nums, int start, int end){
int n = nums.size();
int dp_i_1 = 0, dp_i_2 = 0;
int dp_i = 0;
for(int i = end; i >= start; i--){
dp_i = max(dp_i_1, dp_i_2 + nums[i]);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
};
|
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为
root 。
除了 root
之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
如果两个直接相连的房子在同一天晚上被打劫
，房屋将自动报警。
给定二叉树的 root 。返回在不触动警报的情况下
，小偷能够盗取的最高金额 。
示例：
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释:
小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
结构
1
2
3
4
5
6
7
8
| 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) {}
};
|
思路：
还是和之前一样的套路，我们如果偷了节点，那么他的左右子树就不能偷。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int rob(TreeNode* root) {
if(root == nullptr) return 0;
int do_it = root->val +
(root->left == nullptr ? 0 : rob(root->left->left) + rob(root->left->right)) +
(root->right == nullptr ? 0 : rob(root->right->left) + rob(root->right->right));
int not_do = rob(root->left) + rob(root->right);
int res = max(do_it, not_do);
return res;
}
};
|
备忘录优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
map<TreeNode*, int> memo;
int rob(TreeNode* root) {
if(root == nullptr) return 0;
if(memo[root]){
return memo[root];
}
int do_it = root->val
+ (root->left == nullptr ? 0 : rob(root->left->left) + rob(root->left->right))
+ (root->right == nullptr ? 0 : rob(root->right->left) + rob(root->right->right));
int not_do = rob(root->left) + rob(root->right);
int res = max(do_it, not_do);
memo[root] = res;
return res;
}
};
|
最后一种就是采用树形dp，采用后续遍历的方式，时间复杂度为O(n)，空间复杂度为O(logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int rob(TreeNode* root) {
vector<int> res(2);
res = dfs(root);
return max(res[0],res[1]);
}
vector<int> dfs(TreeNode* root){
if(root == nullptr) return {0,0};
vector<int> left = dfs(root->left);
vector<int> right = dfs(root->right);
int do_it = root->val + left[0] + right[0];
int not_do = max(left[0], left[1]) + max(right[0], right[1]);
return {not_do, do_it};
}
};
|