打家劫舍题一共有三道，首先看看最简单的：

打家劫舍（一）

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷
窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 400

思路

这是一道很明显的动态规划题，规定用数组dp来存储偷窃到的最高金额，数组nums表示每个房子能够偷窃到的金额，那么dp[i]表示从第一个房子到第i个房子能够偷窃到的最高金额，所以

如果选择偷窃这第i个房子，就意味着不能偷窃第i-1个房子，那么偷窃到的最高金额可表示为dp[i]=dp[i-2]+nums[i]。

反之，如果不偷窃这第i个房子，那么dp[i]=dp[i-1]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rob(vector<int>& nums) {
		int size = nums.size();
		if(!size) return 0;
		if(size == 1) return nums[0];
		vector<int> dp(size+1, 0);//初始化记录数组长度为size+1,便于处理边界问题
		dp[0] = 0;//这样，当i为第2个房子时，就可以开始循环
		dp[1] = nums[0];
		for(int i=2; i<size+1; i++)
			dp[i] = max(dp[i-1], dp[i-2]+nums[i-1]);
		return dp[size];
	}
};

打家劫舍（二）

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 :

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃1号房屋（金额=2），然后偷窃3号房屋（金额=2）, 因为他们是相邻的。

思路

除了首尾相连这个要求外，这道题和打家劫舍（一）处处相同。所以，要想办法将这道题转换成第一道题。关键步骤就是如何破除这个圈。我们可以对是否偷窃第一个房子讨论。

如果偷窃第一间房子，那么就一定不能偷窃最后一间房子，那么在去掉最后一间房子后，前面的房子就相当于连成一排的。

同理，如果不偷窃第一间房子，那么最后一间房子是否偷窃是不一定的，问题就转换成了第二间房子到最后一间房子连成一排。

代码实现

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

打家劫舍（三）

题目描述

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

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 :

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \
     3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

思路

这道题变成了树形结构，不能像前面的题那样，用一个记录数组，方便得使用动态规划。但是，选择出能够盗窃到最高金额的方式是很类似的。

我们先假设有一个dp数组，存放的树的最高可盗窃金额，dp[root]表示以root为根的树的最高可盗窃金额。那我们从根节点出发讨论：

我们如果选择盗窃根节点的房间，那么就不能盗窃此根节点的左右子树的根节点，那么能够盗取的最大金额就为
此根节点房间的金额加上左子树的左右子树和右子树的左右子树的金额，即：
root->val + dp[root->left->left] + dp[root->left->right] + dp[root->right->left] + dp[root->right->right]

反之，如果不盗取根节点的房间，那么能盗取的最大金额就为dp[root->left]+dp[root->right]

最后，我们只需要比较这两种选择，谁的金额更大，就能知道哪种选择才是最优的了。

但是，麻烦的问题是，树形结构下，我们并不能很方便的使用dp数组来存储数据。为了遍历树形结构使用递归是比较方便的，所以，直接将某棵树的最高可盗窃的金额作为递归函数的返回值。

代码实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
	vector<int> money;
public:
	int rob(TreeNode* root) {
		return DFS(root);
	}

	int DFS(TreeNode* root) {
		if(!root) return 0;
		int value = 0;
		if(!root->left) value += DFS(root->left);
		if(!root->right) value += DFS(root->right);
		if(!root->left && !root->right) return root->val;
		return max(root->val + DFS(root->left->left) + DFS(root->left->right) + DFS(root->right->left) + DFS(root->right->right), value);
	}
};

这种方法看起来比较容易理解，但是在使用了太多次递归，无论是时间复杂度还是空间复杂度都是不可接受的，所以，可以想办法改进算法。

在上面的算法中，函数DFS(root)返回的值是以root为根的树能够偷窃的最高金额，但是，我们并不知道这个最高金额的偷窃方法到底有没有选择偷窃root这个根，所以在计算的时候，我们需要
DFS(root->left->left)、DFS(root->left->right)…

但是，我们如果让DFS函数的返回值为一个大小为2的数组，DFS(root)[0]表示不选择根节点的时候能够偷窃的最高金额，DFS(root)[1]表示选择根节点的时候能够偷窃的最高金额，那么最后，我们只需要比较这两种方式，哪种的金额更高就好了。

代码实现2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	vector<int> money;
public:
	int rob(TreeNode* root) {
        vector<int> money = DFS(root);
		return max(money[0], money[1]);
	}

	vector<int> DFS(TreeNode* root) {
		if(!root) return {0, 0};
		vector<int> left = DFS(root->left);
		vector<int> right = DFS(root->right);
		vector<int> value(2);
		value[0] = max(left[0], left[1])+max(right[0], right[1]);
		//0表示不选择根节点，那么可以任意选择两个子树
		value[1] = root->val + left[0] + right[0];
		//1表示选择根节点，那么可以不能选择带有根节点的子树
		return value;
    }
};

代码实现3

下面的这个算法，无论是从时间复杂度还是空间复杂度来说，都是非常优秀的，可以借鉴。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rob(TreeNode* root) {
        int l=0, r=0;
        return helper(root, l, r);
    }
    int helper(TreeNode* root, int& l, int& r){//l、r使用的使引用
        if(!root) return 0;
        int ll=0, lr=0, rl=0, rr=0;
        l = helper(root->left, ll, lr);
        r = helper(root->right, rl, rr);
        return max(root->val+ll+lr+rl+rr, l+r);
    }
};

传递引用，可以使得递归过程中的参数共用一个内存空间，这样的话，可以节省内存消耗，同时能够提高速度.