LeetCode 打家劫舍系列(House Robber)

LeetCode上的打家劫舍系列(House Robber)可以说是经典的DP问题,用来练习是再好不过了。

打家劫舍之一 House Robber

原题传送门: https://leetcode.com/problems/house-robber/

首先是问题分解,假设当前已经肆虐过了前i个房子(0...i-1),且rob[i]抢劫了下标为i的房子时的最大收益,pass[i]不抢劫下标为i的房子时的最大收益,那么可以得到状态转移方程:

1
2
rob[i] = nums[i] + pass[i-1]
pass[i] = max(rob[i-1], pass[i-1])

然后据此状态转移方程,再将状态数组简化为只保留前一次的状态(空间复杂度从O(n)降低到O(1)),得题解如下。

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 (len == 0) return 0;
int robLast = nums[0], passLast = 0;
int robCur, passCur;
for (int i = 1; i < len; i++) {
robCur = nums[i] + passLast;
passCur = max(robLast, passLast);
robLast = robCur;
passLast = passCur;
}
return max(robLast, passLast);
}
};

打家劫舍之二 House Robber II

原题传送门: https://leetcode.com/problems/house-robber-ii/

这题可以说跟上一题没有太大区别,无法是把头尾两个房子连起来了,于是头尾两个房子不能同时抢劫而已。

此时只需要分抢劫不抢劫第一个的房子两种情况就可以重用上一题的解题思路了。如果抢劫了第一个房子,则最后的答案只能取不抢劫最后一个房子的情况了;而如果不抢劫第一个房子,则最后的答案应该取抢劫不抢劫最后一个房子的最大值。

假设有0...n-1一共n个房子,circled_solution表示成环的结果,solution表示正常不成环的结果,那么以上的情况分析可以简化为:

1
circled_solution(0...n-1) = max(nums[0] + solution(2...n-2), solution(1...n-1))

当然,我们也可以两种情况下都直接在(0...n-1)这个区间上求解。此时可以用初始条件来控制第一个房子是否抢劫的选择,用整型最小值0x80000000来表示相反的选择,得出如下的题解。

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
class Solution {
public:
int rob(vector<int>& nums) {
int len = nums.size();
if (len == 0) return 0;
if (len == 1) return nums[0];
int result = 0, robLast, passLast, robCur, passCur;
// if rob head
robLast = nums[0], passLast = 0x80000000;
for (int i = 1; i < len; i++) {
robCur = nums[i] + passLast;
passCur = max(robLast, passLast);
robLast = robCur;
passLast = passCur;
}
result = max(result, passLast);

// if pass head
robLast = 0x80000000, passLast = 0;
for (int i = 1; i < len; i++) {
robCur = nums[i] + passLast;
passCur = max(robLast, passLast);
robLast = robCur;
passLast = passCur;
}
result = max(result, max(robLast, passLast));
return result;
}
};

打家劫舍之三 House Robber III

原题传送门: https://leetcode.com/problems/house-robber-iii/

见到二叉树,问题的分解就非常容易了,于是想也不想首先写出递归的题解,如下。

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
/**
* 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 {
int robRoot(TreeNode* root) {
if (root == NULL) return 0;
return root->val + passRoot(root->left) + passRoot(root->right);
}

int passRoot(TreeNode* root) {
if (root == NULL) return 0;
return rob(root->left) + rob(root->right);
}
public:
int rob(TreeNode* root) {
if (root == NULL) return 0;
return max(robRoot(root), passRoot(root));
}
};

但是这个代码提交后提示超时。细细一想就知道原因了,以上的递归代码中存在大量重复执行的代码,使得时间复杂度呈几何式的增长。所以需要进行优化。

因为要进行深度优先遍历,简单的方法还是通过递归,但是为了减少重复的计算,需要自低向上的来计算结果。而每一个子树在经过计算后应该向其父节点传递两个信息:一是抢劫该子树的根节点所获最大收益;二是不抢劫该子树所获最大收益。

为了方便状态通过函数的返回值来传递,直接定义一个简单的结构体RobResult,然后写出DFS的题解,如下。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
struct RobResult {
int rob, pass, res;
RobResult(int rob, int pass) : rob(rob), pass(pass), res(max(rob, pass)) {}
};
class Solution {
const RobResult EMPTY_RESULT = RobResult(0, 0);
RobResult innerRob(TreeNode* root) {
if (root == NULL) return EMPTY_RESULT;
RobResult l = innerRob(root->left);
RobResult r = innerRob(root->right);
return RobResult(root->val + l.pass + r.pass, l.res + r.res);
}
public:
int rob(TreeNode* root) {
if (root == NULL) return 0;
return innerRob(root).res;
}
};