算法6 抢劫

题目：你是一名专业强盗，计划沿着一条街打劫。每间房屋都储存有一定金额的钱，唯一能阻止你打劫的约束条件就是房屋之间有安全系统相连，如果同一个晚上有两间相邻的房屋被闯入，它们就会自动联络警察，因此不可以打劫相邻的房屋。
给出一个表示每个房子的金额的非负整数的列表，确定你今天晚上可以抢救的最大金额，而不提醒警察。
思路：加入int[] sum={1，2，3，4}，在不能抢相邻房子的前提下，
4栋房子我们可以最多抢2栋，即挑选出两个加和最大值 ，在int[] sum={1，2，3，4，5}，5栋房子时我们可以最多可以抢3栋，但是不见得三栋的的和比抢两栋的钱数多。所以要找最大值，又要不相邻，我们需要用到用状态转移方程：sum[i] += Math.max(sum[i-2], sum[i-3]); 即抢第四栋房子时，要在去除抢第一栋或抢第二栋时的最大值。（这个的sum[i-2],并不是那个i-2索引的值而是通过状态转移方程求出的和）。

代码

public static int robber(int[] sum){
    if (sum== null || sum.length == 0) {
        return 0;
    }
    //如果只有一个元素，返回这个元素值
    if(sum.length==1){
        return sum[0];
    }
    else if(sum.length==2){
        //如果有两个元素，返回其中较大的值
        return Math.max(sum[0], sum[1]);
    }else if(sum.length==3){
        //如果有三个元素，比较第一个元素和第三个元素之和与第二个元素的值，返回较大者
        return Math.max(sum[0]+sum[2], sum[1]);
    }
    //把第一个和第三个元素的和赋给第三个元素，以便以后比较
    if (sum.length > 3) {
        sum[2] += sum[0];
    }
    //从第四个元素开始处理就需要用到公式了,也是从第四个开始重新赋值,元素少于四的时候，公式不成立
    int i = 3;
    for(;i<sum.length;i++){
        sum[i] += Math.max(sum[i-2], sum[i-3]);
    }
    //举个例子:如有4个元素，i=3，执行一次循环之后(这个时候i=4):最后一个元素=最后一个元素+前两个中较大的；
    return Math.max(sum[i-1], sum[i-2]);//再比较最后一个和倒数第二个,i-1是最后一个元素因为之前的循环使此时i=sum.length+1
}