leetcode_198:打家劫舍

这个问题的话，我觉得应该是属于贪心算法，反正思路上很明确。假设我们有一个数组flag用来存储各个位置的最大值，且数组长度大于2，那么我们在求第i个最大值时只与两个值有关：第i-1个值和第i-2个值。且flag[i] = Math.max(flag[i-1], flag[i-2]+nums[i])，因为当前的最大值要不然就是前一个的最大值，要不然就是前两个的最大值加上当前的值，只能是这两种情况。所以我们只需要初始化第1个和第2个的值，后面的就可以根据这种贪心策略去获得相应位置的结果。代码如下：

    public int rob(int[] nums) {
    if (nums.length == 1)return nums[0];else if (nums.length == 2)return Math.max(nums[0], nums[1]);else if (nums.length == 0)return 0;int flag[] = new int[nums.length];flag[0] = nums[0];flag[1] = Math.max(nums[0], nums[1]); //初始化前两个值，第二个是两者的最大值for(int i = 2; i < nums.length; ++i) {
      //贪心的去更新flag[i] =  Math.max(nums[i]+flag[i-2], flag[i-1]);}return flag[nums.length-1]; //返回最后的结果}

当然这个题目有可以优化的地方，因为我们能看到在更新flag数组的时候我们总是利用当前位置的前1个和前2个元素， 所以不需要flag数组，只需要两个元素记住这两个状态就行了。