2017-03-10

JavaScript 版动态规划算法题：打家劫舍

今天，我们要讲的是一道动态规划算法题：打家劫舍。这道题有三个版本，它们都来自 LeetCode：

https://leetcode.com/problems/house-robber

https://leetcode.com/problems/house-robber-ii

https://leetcode.com/problems/house-robber-iii

本文将先介绍动态规划的基础知识，然后使用动态规划思想解决这个问题，所用的语言仍然是 JavaScript。

动态规划简介

动态规划是(Dynamic Programming，DP)是一种将复杂问题分解成更小的子问题来解决的优化技术。那么具体哪些算法用到了动态规划呢？使用动态规划的算法很多，先列举一个简单的吧！

求斐波那契数列：

function fibonacci(num) {
  if (num === 1 || num === 2) {
    return 1;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}

上述函数将 fibonacci(num) 分解成 fibonacci(num - 1) 和 fibonacci(num - 2)，然后继续分解直到 num 为1或2时终止。

动态规划和分而治之的区别

了解了动态规划，我们来看另一种思想——分而治之。分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：

把它分成两个或多个更小的问题；
分别解决每个小问题；
把各小问题的解答组合起来，即可得到原问题的解答。

小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

动态规划和分而治之都是大问题分解成多个子问题，那么这两者有什么区别呢？动态规划和分而治之的区别在于子问题之间是否独立。分而治之是把问题分解成相互独立的子问题，然后组合它们的答案，而动态规划则把问题分解成相互依赖的子问题。

常见的使用分而治之的算法有归并排序和快速排序。具体实现代码可以参考前面的博文《JavaScript 版数据结构与算法（九）排序和搜索》。

用动态规划解决“打家劫舍问题”

通过前面的介绍，大家应该对动态规划有个大致的了解了，下面让我们用动态规划来解决“打家劫舍问题”。“打家劫舍问题”的题目是：

假设你是一个专业的劫匪，你计划去打劫一条街上的家舍。每家有一定数量的钱财，但相邻两家有一个彼此连接的安全系统。一旦相邻两家在同一晚被打劫，那么这个安全系统就会自动报警。

给你一个由非负整数组成的数组，用来代表每家的钱财，在不让安全系统自动报警的前提下，求你能打劫到的钱财的最大数量。

我们还是用单元测试来表达一下需求吧！毕竟好多程序员看机器语言要比自然语言还舒服：

1 2	// 对于 [2, 0, 0, 4, 5]，能打劫到的最大钱财是7 expect(rob([2, 0, 0, 4, 5])).toBe(7);

我们要编写一个 rob 方法，可以返回内部数组的最大的不相邻数字之和。

那么如何实现这个算法呢？我们需要借助动态规划思想：

如果数组长度为1，那么直接返回数组唯一项。
如果数组长度为2，那么返回“第1项”和“第2项”的较大者。
如果数组长度为3，那么返回“数组长度为1的结果+第3项”与“数组长度为2的结果”的较大者。
如果数组长度为4，那么返回“数组长度为2的结果+第4项”与“数组长度为3的结果”的较大者。
……
如果数组长度为n，那么返回“数组长度为n-2的结果+第n项”与“数组长度为n-1的结果”的较大者。

为何会如此呢？因为题目要求不能打劫相邻两家，所以数组的当前项只能和上上次的结果相加。那么子问题就是“数组长度为n-2的结果+第n项”与“数组长度为n-1的结果”。用方程来表示就是：

1
2
3

f(0) = array[0]
f(1) = max(array[0], array[1])
f(n) = max( f(n-2) + array[n], f(n-1) )

所以实现代码就是：

LeetCode/198-rob1.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  var last = 0,
    now = 0;
  for (var i = 0; i < nums.length; i++) {
    var temp = last;
    last = now;
    now = Math.max(temp + nums[i], now);
  }

  return now;
};

圆圈版打家劫舍

“打家劫舍”问题还有另一个版本，它的题目是：

在上次打劫后，作为专业劫匪的你意识到自己需要去一个新的地方打劫，这样才不会引起太多注意。这次，你去的地方的家舍是按圆圈形状来排列的。这意味着第一家和最后一家是挨着的，同时，安全系统和上个地方的一样。

给你一个由非负整数组成的数组，用来代表每家的钱财，在不让安全系统自动报警的前提下，求你能打劫到的钱财的最大数量。

那么这道题该如何解答呢？因为家舍首尾相连，所以你不能在同一晚打劫第一家和最后一家，既然不能打劫，机智的你索性将计就计，先排除最后一家不管，或者先排除第一家不管，打劫剩余的家舍，然后比较那个更划算。所以这道题可以这么来解答：

先求出第一家到倒数第二家的最大钱财数量
然后求出第二家到最后一家的最大钱财数量
最后求两者的较大值

所以实现代码就是：

LeetCode/213-rob2.js

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  var rob1 = require('./rob1');

  if (nums.length === 1) {
    return nums[0];
  }
  return Math.max(rob1(nums.slice(1)), rob1(nums.slice(0, nums.length - 1)));
};

上述代码中，nums.slice(1)代表排除了第一家，nums.slice(0, array.length - 1)代表排除了最后一家。然后运行测试，发现确实没有上次打劫的多：

1	expect(rob([2, 0, 0, 4, 5])).toBe(6);

二叉树版打家劫舍

我们再看一道二叉树版打家劫舍吧！题目如下：

作为专业劫匪的你又找到了一个新地方可以下手，这个地方的家舍是按二叉树形状排列的，安全系统和之前一样。在不让安全系统自动报警的前提下，求你能打劫到的钱财的最大数量。

为了表述题意，我们来看个例子吧：

那么最大钱财就是第一行的3和第三行的3、1，一共是7。

看完了题目，我们该如何编写代码呢？首先，按照动态规划，我们需要找到子问题！在第一版的打家劫舍问题中，子问题是“数组长度为n-2的结果+第n项”与“数组长度为n-1的结果”的较大者。那么这道题的子问题是什么呢？这道题的子问题是“打劫当前节点”和“不打劫当前节点”哪个更划算？那么如何比较哪个更划算呢？这得看“打劫子节点”和“不打劫子节点”的值各是多少。如果“打劫当前节点”，那么就不能打劫子节点，那么这时值就是“不打劫子节点”的值加上自己值。如果“不打劫当前节点”，那么就可以打劫子节点，也可以不打劫子节点，那么这时值就是“打劫子节点”和“不打劫子节点”的值的较大者。用代码表示就是：

LeetCode/337-rob3.js

/**
 * Definition for a binary tree node.
 * function TreeNode(key) {
 *     this.val = key;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
  var dfs = function (node) {
    if (node === null) {
      return [null, null];
    }
    var left = dfs(node.left);
    var right = dfs(node.right);
    var res = [];
    res[0] = left[1] + right[1] + node.key;
    res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return res;
  };

  var num = dfs(root);
  return Math.max(num[0], num[1]);
};

我们首先写一个 dfs来深度优先遍历节点，其实就是先序遍历。这个 dfs 方法返回了“打劫当前节点”和“不打劫当前节点”的值各是多少，这里用 res 数组来表示。由于深度优先遍历是对左右节点也进行 dfs，所以我们可以通过子节点的返回值（这里用 left 和 right来表示）得到当前节点的返回值，直到节点为空，就把递归终结掉！编写完了 dfs，我们对 root 入口进行 dfs，得到的数组就是“打劫根节点”和“不打劫根节点”的数值。最后，返回较大者即可得到答案。

测试代码如下：

LeetCode/_tests_/337-rob3.test.js

var rob = require('../rob3');
var BinarySearchTree = require('../../Tree/BinarySearchTree');

test('rob3', function () {
  var binarySearchTree = new BinarySearchTree();

  binarySearchTree.insert(11);
  binarySearchTree.insert(7);
  binarySearchTree.insert(13);
  binarySearchTree.insert(5);
  binarySearchTree.insert(3);
  binarySearchTree.insert(9);

  expect(rob(binarySearchTree.getRoot())).toBe(27);
});