大家好，我是前端西瓜哥。

今天我们做一道非常经典的动态规划题——打家劫舍，适合用来入门动态规划。

题目描述

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

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

示例：

输入：[1,2,3,1]

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

解题

动态规划（dynamic programming）是一个将问题拆分成子问题，通过解决子问题最终解决原问题的一种解法。

和分治法的子问题相互独立不同，动态规划的子问题是重叠的，多个子问题可能依赖相同的一个子子问题。

动态规划（dynamic programming）的 programming 指的是 “表格”，因为我们经常会构建一个二维数组来记录每个阶段的变化。有时候我们不需要记录过去阶段的状态，倒是可以改用一维数组，降低一下空间复杂度。

动态规划题的解法通常有两种实现方式：

1. 迭代（自底向上）
2. 递归 + 备忘录（自顶向下）

接下来我们就用这两种方式来解题。

迭代法

迭代法，需要用到状态转移表，就是前面提到的 programming（表格），来记录子问题向父问题的状态转移变化。

根据题意的限制，相邻的房屋不能同时选择，所以对于第 i 个房屋，我们有两种方案：

1. 选择抢当前房屋，将抢到的金额，加上抢到前前一个房间的最大金额
2. 不选择当前房屋，此时金额为抢到前一个房屋时的最大金额

这两种选择，选择其中金额大的，就是抢到第 i 个房屋的最大金额。

我们的状态转移方程式为：

dp[i] = Max(dp[i - 1], dp[i - 1] + curRob)

代码实现如下：

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

  const dp = new Array(nums.length);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[dp.length - 1];
};

这里需要初始化 dp[0] 和 dp[1]，否则我们的 dp[i - 2] 就会越界。

时间复杂度 O(n)，空间复杂度 O(n)。

对于初始化，还有更优雅的写法：

function rob(nums): number {
  const n = nums.length;
  const dp = new Array(n + 2);
  dp[n] = 0;
  dp[n + 1] = 0;
  for (let i = n - 1; i >= 0; i--) {
    dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
  }
  return dp[0];
};

我们给状态数组末尾多加两个值为 0 的数组元素，然后逆向迭代数组元素。这样就不需要初始化最前面的两个元素了。

优雅，实在是优雅。

读者可能也观察到了，其实我们这个代码实现并不需要整个数组元素，只需要两个元素就够了。

function rob(nums): number {
  const n = nums.length;
  let lo = 0;
  let hi = 0;
  for (let i = n - 1; i >= 0; i--) {
    const cur = Math.max(nums[i] + lo, hi);
    lo = hi;
    hi = cur;
  }
  return hi;
};

这样，时间复杂度就又从 O(n) 下降到了 O(1)，已经是最优解。

递归 + 备忘录

思路依旧是迭代的思路，只是换成了递归的形式。

function rob(nums): number {
  const memo = new Array(nums.length);
  return robByIndex(nums, memo, nums.length - 1);
};

function robByIndex(nums, memo, i): number {
  if (i < 0) return 0;
  if (memo[i] !== undefined) return memo[i];

  memo[i] = Math.max(
    robByIndex(nums, memo, i - 1),
    robByIndex(nums, memo, i - 2) + nums[i]
  )
  return memo[i];
}

memo 备忘录的作用是缓存，因为多个子问题可能依赖相同的子子问题，会导致很多重复的迭代。如果不做缓存，就变成回溯了，时间复杂度非常高。

这种解法因为用了备忘录做了很多剪枝，时间复杂度其实也是 O(n)。

因为使用了备忘录，并有多层调用栈，空间复杂度是 O(n)。

总结

动态规划的常规解法有两种。

一种是构造 programming，即表格，通常为二维数组，记录迭代过程中的状态。二维数组可以根据实际情况，降维为一维数组或几个变量，本文的题目就成功降低维度为两个变量。

还有一种是递归的方式，因为动态规划的问题通常会有重叠的子问题，所以我们往往需要一个备忘录记录我们曾经走过的路。

如果没有备忘录，其实就是回溯了，时间复杂度会高很多。

回溯问题多为找所有解的问题，所以并不会有重复递归的情况。而动态规划多为求最值问题，只需要知道递归的最值就行了，其中有什么组合我们并不关心，所以要用备忘录。

当然，上面这些都是实现套路，动态规划最难的是找出状态转移方程式，即应该通过怎样的维度将问题做拆分，并找出当前阶段的状态怎么通过之前阶段的状态转移过来。

我是打算每周一到周五做五道算法题，结果常常是周六日连做五道的前端西瓜哥。

欢迎关注我，学习更多的前端和算法相关的知识。