打家劫舍问题

数据结构和算法-动态规划（打家劫舍）定位为求最值的问题，从入门阶动态规划到引入其他数据结构的演变之路，你看打劫问题就够了。

198. 打家劫舍

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

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

面试题 17.16. 按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

这俩道题很典型，算是超级简单的动态规划求最值问题了，从题目出发，小偷只能间隔作案，按摩师也是间隔服务，所谓换汤不换药，其实是一个题，所以放一起说了，爬楼梯那一章，我们学会了从base出发找最值，这里也是同样，为了方便记忆，我列一个表来进行子问题推导

盗窃休息	第一天	第二天	...	第N天
盗窃	nums[0]	昨日休息今天偷	...	N-1=休息第N天偷
休息	Integer.MIN_VALUE	Math.max(上一次休息,上一次盗窃)	...	Math.max(上一次休息,上一次盗窃)

最后呢去取休息和盗窃的最大值，就是小偷最大的收获，或者是按摩师最大的收入。
根据推导过程，仔细分析，写出代码。打劫I，就这这么处理了，按摩女郎也处理了。


public int maxPilferValue(int[] nums){
     if(nums.length==0) return 0;
        int pilfer=nums[0];
        int rest=0;
    for(int i=1;i<nums.length;i++){
        int newRest=Math.max(pilfer,rest);
        int newPilfer=rest+nums[i];
        pilfer=newPilfer;
        rest=newRest;
    }
     return Math.max(pilfer,rest);
}

213. 打家劫舍 II

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

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

看到第二题了。你是不有点懵逼了，我该怎了考虑偷盗呢，2种情况，我不偷第一个屋子的，拿到最大的金额和不偷最后一个屋子拿到的最大金额求最大，这不就是我能在不被警报发现拿到最大的金额吗。偷鸡行为。把问题简化为求俩遍打劫I问题。

public int maxAPilferValue(int[] nums){
     if(nums.length==0) return 0;
        int pilfer=nums[0];
        int rest=0;
    for(int i=1;i<nums.length-1;i++){
        int newRest=Math.max(pilfer,rest);
        int newPilfer=rest+nums[i];
        pilfer=newPilfer;
        rest=newRest;
    }
     return Math.max(pilfer,rest);
}
public int maxBPilferValue(int[] nums){
     if(nums.length==0) return 0;
        int pilfer=0;
        int rest=0;
    for(int i=1;i<nums.length;i++){
        int newRest=Math.max(pilfer,rest);
        int newPilfer=rest+nums[i];
        pilfer=newPilfer;
        rest=newRest;
    }
     return Math.max(pilfer,rest);
}
public int maxPilferValue(int[] nums){
return Math.max(maxAPilferValue(nums),maxBPilferValue(nums));
}

337. 打家劫舍 III

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

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

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

分析题目：树形动态规划，二叉树，离不开dfs。心中已有乾坤。想到二叉树脑海中就浮现了,二叉树解决问题的伪代码。

public int[] traverseTree(TreeNode root){
	if (root == null) {
            return new int[]{0,0};
        }
	int[] leftTemp=traverseTree(root.left);
	int[] rightTemp=traverseTree(root.right);
	// 这里要处理打劫。这TM不是后序遍历吗
}

当root被选中的时候，他的left和right都无法被选中，当left被选中，可以选择right，反之也一样可以选取left；来进一步完善代码

public int[] traverseTree(TreeNode root){
	if (root == null) {
            return new int[]{0,0};
        }
	int[] leftTemp=traverseTree(root.left);
	int[] rightTemp=traverseTree(root.right);
	int[] dp=new int[2];
	//打劫，root的左右无法被选中
	dp[1]=root.val+leftTemp[0]+rightTemp[0];
	//不打劫，休息的情况看之前的打劫最大值。
	dp[0]= Math.max(leftTemp[0], leftTemp[1]) + Math.max(rightTemp[0],rightTemp[1]);
	// 这里要处理打劫。这TM不是后序遍历吗
	return dp;
}