打劫房屋是典型的动态规划问题，面试经常考，LintCode 上有 3 道题，总结一下做法。
打劫房屋 I
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。
样例给定 [3, 8, 4], 返回 8.
思路动态规范，初始状态：
v[i] 表示第 i 个房子里的钱，dp[i] 表示打劫到第 i 个房子时获得的最大利润 则 dp[0] = v[0]，dp[1] = max(v[0], v[1])。
状态转移：
由于不能抢相邻的房屋，则抢第 i 间房子就不能抢第 i - 1 间房子，就要比较一下抢这间是否划算。
所以 dp[i] = max(v[i] + dp[i - 2], dp[i - 1]);
由于 dp[i] 只跟 dp[i - 1] 和 dp[i - 2] 有关，所以每一步只要保存这两个值就行了。
class Solution { public: /** * @param A: An array of non-negative integers. * return: The maximum amount of money you can rob tonight */ long long houseRobber(vector<int> A) { // write your code here long long pre = 0; long long cur = 0; long long tmp; for(int i = 0; i < A.size(); ++i){ tmp = max(pre + A[i], cur); pre = cur; cur = tmp; } return cur; } }; 打劫房屋 II在上次打劫完一条街道之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子围成了一个圈，这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。
思路和打劫房屋 I 比只是多了个首尾不能同时取的限制，所以可以用一样的算法先算一次取首不取尾的结果，再算一次不取首的结果，看看哪个大。
class Solution { public: /** * @param nums: An array of non-negative integers. * return: The maximum amount of money you can rob tonight */ int houseRobber2(vector<int>& nums) { // write your code here if(!nums.size()) return 0; int t1 = sub(nums, 1, nums.size() - 1); int t2 = nums[0] + sub(nums, 2, nums.size() - 2); return max(t1, t2); } int sub(vector<int>& nums, int start, int end) { int pre = 0; int cur = 0; for(int i = start; i <= end; ++i) { int t = max(pre + nums[i], cur); pre = cur; cur = t; } return cur; } }; 打劫房屋 III在上次打劫完一条街道之后和一圈房屋之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子组成的区域比较奇怪，聪明的窃贼考察地形之后，发现这次的地形是一颗二叉树。与前两次偷窃相似的是每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。
算一算，如果今晚去打劫，你最多可以得到多少钱，当然在不触动报警装置的情况下。
样例 3 / \ 2 3 \ \ 3 1窃贼最多能偷窃的金钱数是 3 + 3 + 1 = 7.
思路这次把数组换成了二叉树，用层序的方式看二叉树，则问题变成打劫了第 i 层 就不能打劫第 i - 1 层，也可以用打劫房屋 I 的方法来做了。
用递归的方式计算打劫到第 i 层的最大收益。
class Solution { public: /** * @param root: The root of binary tree. * @return: The maximum amount of money you can rob tonight */ int houseRobber3(TreeNode* root) { // write your code here int t1 = 0; return sub(root, t1); } int sub(TreeNode* node, int& pre) { if(!node) return 0; int pre1 = 0; int pre2 = 0; int cur = sub(node->left, pre1) + sub(node->right, pre2); //上一层的最大收益 int t = max(node->val + pre1 + pre2, cur); //pre1 + pre2 为上两层的最大收益 pre = cur; return t; } };
