标签归档:leetcode

leetcode198. 打家劫舍

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

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

初看这题想到的解法是直接两次循环,按奇偶性获取两个和,得出最大值。实际是错误的解法。因为对于 [2, 1, 1, 2] 这样的数据是不正确的。

动态规划三步骤:

  1. 找重复子问题
  2. 定义状态
  3. DP 方程

$a[$i] 表示从 0…i 房子间能偷盗的最大值,$a[$i][0] 表示 $i 的房子没偷的最大值,$a[$i][1] 表示 $i 的房子偷了的最大值。如果只是使用一维数组存储状态,$a[$i] = $a[$i-1] + $nums[$i] 表示偷盗 $i 房子的最大值是不可以的,因为不能确定前一个房子有没有偷。

function rob($nums)
{
  if (!$nums) {
    return 0;
  }
  $n = count($nums);
  $a = [];
  $a[0][0] = 0;
  $a[0][1] = $nums[0];
  for ($i = 1; $i < $n; $i++) {
    $a[$i][0] = max($a[$i-1][0], $a[$i-1][1]);
    $a[$i][1] = $a[$i-1][0] + $nums[$i];
  }
  return max($a[$n-1][0], $a[$n-1][1]);
}

我们可以只存储偷盗每个房子时是否偷取的最大值,这样就从二维数组降到了一维:

function rob($nums)
{
  if (!$nums) {
    return 0;
  }
  $n = count($nums);
  if ($n == 1) {
    return $nums[0];
  }
  $a[0] = $nums[0];
  $a[1] = max($nums[0], $nums[1]);
  $res  = max($a[0], $a[1]);
  for ($i = 2; $i < $n; $i++) {
    $a[$i] = max($a[$i - 1], $a[$i - 2] + $nums[$i]);
    $res   = max($res, $a[$i]);
  }
  return $res;
}

数组都可以不用,我们可以直接使用三个变量存储:

function rob($nums)
{
  if (!$nums) {
    return 0;
  }
  $n = count($nums);
  if ($n == 1) {
    return $nums[0];
  }
  $first = $nums[0];
  $second = max($nums[0], $nums[1]);
  for ($i = 2; $i < $n; $i++) {
    $temp = $second;
    $second = max($second, $first + $nums[$i]);
    $first = $temp;
  }
  return $second;
}

下面是终极代码,初看完全没有头绪:

function rob($nums)
{
  $curMax = $prevMax = 0;
  foreach ($nums as $x) {
    $temp = $curMax;
    $curMax = max($curMax, $prevMax + $x);
    $prevMax = $temp;
  }
  return $curMax;
}