【嘎】数组-打家劫舍

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

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

示例 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 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber

下面开始了错误的解答：

class Solution {
    public int rob(int[] nums) {
        int res = 0;
        
        if (nums == null || nums.length == 0) {
            return res;
        }
        
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else {
            int count1 = 0;
            int count2 = 0;
            for (int i = 0; i < len; i += 2) {
                count1 += nums[i];
            }
            for (int j = 1; j < len; j += 2) {
                count2 += nums[j];
            }
            res = count1 > count2 ? count1 : count2;
        }
        return res;
    }
}

我想的太简单了，就会遇到 [2,1,1,2] 的情况报错，看评论说动态规划，还是没有什么概念，刷到一个一开始想法一样的胖友，他是c++的

很容易想到要不是相邻的话，那么就是奇数和偶数各自求和取最大值，但是有点情况不是奇偶最优的，比如2，1，1，2这种需要另外一种思路，每次求和将奇数和偶数比较取最大值，然后再去相加。

class Solution {
public:
    int rob(vector<int>& nums) {
        int sum0 = 0, sum1 = 0;
        
        for(int i = 0; i < nums.size(); ++i)
        {
            if(i % 2 == 0)
            {
                sum0 += nums[i];
                sum0 = max(sum0, sum1);
            }
            else
            {
                sum1 += nums[i];
                sum1 = max(sum0, sum1);
            }
        }
        return max(sum0, sum1);
    }
};

PS： 奇偶判断  不要使用 i % 2 == 1 来判断是否是奇数，因为i为负奇数时不成立，请使用 i % 2 != 0 来判断是否是奇数，或使用 高效式 (i & 1) != 0（i为奇数）来判断。 

然后照着这个思路写了个java的

class Solution {
    public int rob(int[] nums) {
        int res = 0;
        
        if (nums == null || nums.length == 0) {
            return res;
        }
        int sum1 = 0;
        int sum2 = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (i % 2 == 0) {
                sum1 += nums[i];
                sum1 = sum1 > sum2 ? sum1 : sum2;
            } else {
                sum2 += nums[i];
                sum2 = sum1 > sum2 ? sum1 : sum2;
            }
        }
        res = sum1 > sum2 ? sum1 : sum2;
        return res;
    }
}

也就是遍历整个数组，奇数偶数这样加下去，每加一次都取奇数偶数中的最大值。

 取两者之间的最大值还有：Math.max(nums[0],nums[1]);

下面是官网的动态规划算法：

public int rob(int[] num) {
    int prevMax = 0;
    int currMax = 0;
    for (int x : num) {
        int temp = currMax;
        currMax = Math.max(prevMax + x, currMax);
        prevMax = temp;
    }
    return currMax;
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode/
来源：力扣（LeetCode）