打家劫舍-简单

难度：简单

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

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

示例：

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

1
2
3
4

解题思路：

将问题分解成最优子问题；
用递归的方式将问题表述成最优子问题的解；
自底向上的将递归转化成迭代；（递归是自顶向下）;

对于连续的 nn 栋房子：H~1~,H~2~,H~3~......H~n~H 1 ,H 2 ,H 3 ......H n ，小偷挑选要偷的房子，且不能偷相邻的两栋房子，方案无非两种：
方案一：挑选的房子中包含最后一栋；
方案二：挑选的房子中不包含最后一栋；
获得的最大收益的最终方案，一定在这两种方案中产生，用代码表述就是：

var robTo = function (nums, lastIndex) {
  if (lastIndex === 0) {
    return nums[0];
  }

  // 方案一，包含最后一栋房子，则应该丢弃倒数第二栋房子
  let sum1 = robTo(nums, lastIndex - 2) + nums[lastIndex];

  // 方案二，不包含最后一栋房子，那么方案二的结果就是到偷到 lastIndex-1 为止的最优结果
  let sum2 = robTo(nums, lastIndex - 1);

  return Math.max(sum1, sum2);
};

var rob = function (nums) {
  return robTo(nums, nums.length - 1);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var rob = function (nums) {
  if (nums.length === 0) {
    return 0;
  }
  if (nums.length === 1) {
    return nums[0];
  }

  // 仍然用两个变量来存储方案一和方案二的最优结果
  // 不同的是，这次从0开始，lastIndex 取最小值 1
  let sum1 = nums[0];
  let sum2 = nums[1];

  // 然后通过迭代不断增大 lastIndex，过程中维护新的sum1，sum2，直到数组末尾
  for (let lastIndex = 2; lastIndex < nums.length; lastIndex++) {
    let tmp = sum1;

    // 此时的方案一就是上一步中的方案二，
    // 但要求的是最优解，所以要判断前一步的 sum1 和 sum2 哪个更大
    if (sum2 > sum1) {
      sum1 = sum2;
    }

    // sum2 是包含最后一栋房子的方案，
    // 每向后增加一栋房子，就是前一步的 sum1（不包含 lastIndex - 1 ）
    // 加上当前 lastIndex 栋房子的金钱
    sum2 = tmp + nums[lastIndex];
  }

  return sum1 > sum2 ? sum1 : sum2;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

← 打家劫舍 II-中等买卖股票的最佳时机含手续费-困难 →

# 打家劫舍-简单

打家劫舍-简单