【Leetcode】打家劫舍系列全部详细题解

打家劫舍

题目链接

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

样例输入

[2,7,9,3,1]

样例输出

12

样例解释

偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路

这是一道很简单的动态规划问题。每个房子都有两个状态,偷与不偷。
以下方程中二维数组的0表示不偷当前房子,1表示偷当前房子
假设第i间房间偷的话,那最大收益的方程为dp[i][1] = dp[i-1][0] + nums[i];
假设第i间房间不偷的话,那最大收益的方程为dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
将状态转移方程推导出来后用代码实现就是很简单的事情了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (0 == len)
return 0;
int dp[len][2];
memset(dp, 0, sizeof(dp));
dp[0][1] = nums[0];
for (int i = 1; i < len; i++){
dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
dp[i][1] = dp[i-1][0] + nums[i];
}
return max(dp[len-1][0], dp[len-1][1]);
}
};

打家劫舍 II

题目链接

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

样例输入

[1,2,3,1]

样例输出

4

样例解释

你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

解题思路

我们发现,这道题目跟上道题目唯一区别在于首尾相连。在上一道题目中当我们最后一间房子偷的话,那么第一间房子的状态我们是无法得知的。其实想要得知第一间房子的状态一点都不难,我们从后往前也做一次一样的dp即可。只要比较从后面到前面dp时第一间房子不偷的时候的最大值是否跟从前面往后面偷的时候最后一间房子偷时得到的最大一样即可。

AC代码

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
27
28
29
30
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (0 == len)
return 0;
if (1 == len)
return nums[0];
int dp[len][2];
memset(dp, 0, sizeof(dp));
dp[0][1] = nums[0];
for (int i = 1; i < len; i++){
dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
dp[i][1] = dp[i-1][0] + nums[i];
}
int dp_behind[len][2];
memset(dp_behind, 0, sizeof(dp_behind));
dp_behind[len-1][1] = nums[len-1];
for (int i = len-2; i >= 0; i--){
dp_behind[i][0] = max(dp_behind[i+1][1], dp_behind[i+1][0]);
dp_behind[i][1] = dp_behind[i+1][0] + nums[i];
}
if (dp[len-1][1] == dp_behind[0][0]){
return max(dp[len-1][1], dp[len-1][0]);
}
else{
return max(dp[len-1][0], dp_behind[0][0]);
}
}
};

打家劫舍 III

题目链接

题目描述

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。
计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

样例输入

[3,2,3,null,3,null,1]

样例输出

7

样例解释

小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

解题思路

对于每一个节点都有偷或者不偷两种情况,只要分别算出这两个状态的所可以得到的最优解然后比较即可。我们对两个状态单独分析:
我们假设findAns(root)函数用来计算root结点为根的子树所可以获得的最大收益
当前节点偷的最大收益为:

1
root->val + findAns(root->left->left) + findAns(root->left->right) + findAns(root->right->left) + findAns(root->right->right)

当前节点不偷的最大收益为:

1
findAns(root->left) + findAns(root->right)

细心的同学已经看出来,同一个节点可能会被递归多次。为了让我们的程序可以得到进一步的优化,我们可以用一个map来存取每个节点可以获得的最大收益。那再次递归到同一个节点,我们可以直接返回结果,无需重复计算。

AC代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode *, int> maxValue;
//maxValue[root]用于标记在root节点下能够偷取的最大值
//之所以要用map来存取是因为同一个root节点可能会被多次递归进去
//所以当第二次递归进去时我们不会重新算,而是在map里将值取出来
int findAns(TreeNode* root){
if (root == NULL)
return 0;
else if(maxValue.count(root) > 0){
return maxValue[root];
}
int temp1 = root->val;
if (root->left){
temp1 += findAns(root->left->left) + findAns(root->left->right);
}
if (root->right){
temp1 += findAns(root->right->left) + findAns(root->right->right);
}
int temp2 = findAns(root->left) + findAns(root->right);
maxValue[root] = max(temp1, temp2);
return maxValue[root];
}
int rob(TreeNode* root) {
if (root == NULL)
return 0;
findAns(root);
return maxValue[root];
}
};
-------------本文结束您的阅读与肯定是我持续装*的最大动力-------------