打家劫舍系列问题

发现打家劫舍问题主要在于状态转移方程系列的构建，主要要理清下面几个关键点：

• 分析每个房间的状态，构建出状态转移方程
• 不用纠结哪个该偷哪个不该偷，考虑每个房间偷与不偷即可
• “考虑” 不等于 “偷”，具体房间偷与不偷交给递推公式去抉择

打家劫舍 I

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

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

代码实现

var rob = function (nums) {
  const dp = new Array(nums.length + 1).fill(0);
  dp[1] = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    //要么偷这个房间，要么不偷这个房间
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  }
  return dp[nums.length];
};

打家劫舍 II

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

代码实现

var rob = function (nums) {
  if (nums.length === 1) return nums[0];
  //分为两种情况
  //偷第一个房间
  const dp = new Array(nums.length + 1).fill(0);
  //不偷第一个房间
  const dp2 = new Array(nums.length + 1).fill(0);
  dp[1] = nums[0];
  for (let i = 2; i <= nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i - 1]);
  }

  return Math.max(dp[nums.length - 1], dp2[nums.length]);
};

打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。

除了root之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

代码实现

var rob = function (root) {
  const dfs = (node) => {
    if (!node) return [0, 0];
    const left = dfs(node.left);
    const right = dfs(node.right);
    // 偷当前节点
    const rob = node.val + left[0] + right[0];
    // 不偷当前节点
    const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

    return [notRob, rob];
  };
  const res = dfs(root);
  return Math.max(res[0], res[1]);
};