“动态规划”之打家劫舍（leetcode198）

这是一道经典的动态规划算法题，具体的说这是一道线性规划的算法题，我们只要保存好之前的最优解，之后的最优解就是当前的值加之前的最优解，这是一般的解题思路，现在我们来具体看看这个题目。

思路：题目告诉我们会给我们一个数组，这个数组里面的内容代表了标号为下标的房屋的价值，小偷会偷取这些房屋，但是这些房屋有报警系统，如果小偷连续偷了两家就会触发报警，所以这里面有一个条件就是我们在算最大价值的时候是不能连续的，下面来看具体情况。

1. 当数组的内容只有1个时，那么最大价值就是这个房子的价值，我们直接返回 nums[0]

2. 当数组的内容只有两个时，由于不能连续，我们只能选择里面价值大的那个,直接返回Math.max(nums[0], nums[1])

3. 当数组的内容达到三个时，这个时候就出现了两种情况的选择，我们可以选择nums[0] + nums[2]或者选择nums[2]；这个时候我们可以发现偷与不透第i间房，会影响价值的判断，如果偷的话那么就把第i间房的价值加上之前i-2间房子偷的最大值，也可以选择不偷，也就是说只要i-1间房子的最大值，我们对比这两个谁大，那么就把这个值记录起来到一个数组，这个数组专门保存偷到第i间房时的总价值 max = Math.max(arr[i-1], arr[i-2] + arr[i])

代码

var rob = function(nums) {
  const n = nums.length
  let arr = [] // 保存之前的最优解 arr[1]表示nums[0]到nums[1]的最优解
  arr[0] = nums[0]
  arr[1] = Math.max(nums[0], nums[1])
  if(n===1) {
    return arr[0] // 当只有一个元素时显然最优解是这个元素本身
  }

  if(n===2) {
    return arr[1] // 当只有两个元素时选择最大的那一个
  }
  
  // arr[2] 当数组为三个的时候最优解可能是nums[0] + nums[2]也可能是nums[1]
  // arr[3] 当数组为四个的时候最优解可能是nums[0] + nums[2] 也可能是nums[1]+nums[3]
  // 由于arr数组里面保存的状态都是符合要求的也就是说不会发生连续的情况，当求第n个元素时的最优解
  // 不就是这个元素本身的大小加上这个元素前面的前面的那个的最优解之和和前一个元素最优解之和取最大值吗？
  for(let i=2;i<n;i++){
    arr[i] = Math.max(nums[i] + arr[i-2], arr[i-1])
  }
  return arr[n-1]
};

仔细发现我们这个数组是可以不创建的，因为每一次便利我们只拿取了前面的两个内容，所以我们只需要用两个变量分别来保存arr[i-2]和arr[i-1]就行，也称之为滑动数组。

// 由于每次都要创建一个数组，而我们每次只关心前两次的最优解，所以用两个变量保存起来，也就是滚动数组

function rob2(nums) {
  const n = nums.length
  if(n===1) return nums[0]
  if(n===2) return Math.max(nums[0], nums[1])

  let first = nums[0],second = Math.max(nums[0], nums[1])

  for(let i = 2;i<n;i++) {
    // 本次计算的最优解将会变成下一次的second,而本次的second会变成下一次的first
    let temp = second // 保存本次的second
    second = Math.max(first + nums[i], second)
    first = temp
  }
  return second
}

这样我们减少了数组的创建，从而减少了空间复杂度。