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)是一种将复杂问题分解成更小的子问题来解决的优化技术。那么具体哪些算法用到了动态规划呢?使用动态规划的算法很多,先列举一些简单的吧!比如:

1,求斐波那契数列:

1
2
3
4
5
6
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时终止。

2,深度优先遍历(DFS):

  • 先访问一个顶点,然后对相邻顶点挨个进行深度优先遍历。

上述做法将复杂的图遍历分解为“每个顶点的访问相邻顶点的深度优先遍历”。有点类似于二叉树先序遍历。具体代码请参考前面的博文《 JavaScript 版数据结构与算法(八)图 》

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

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

  1. 把它分成两个或多个更小的问题;
  2. 分别解决每个小问题;
  3. 把各小问题的解答组合起来,即可得到原问题的解答。

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

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

常见的使用分而治之的算法有归并排序快速排序。具体实现代码可以参考前面的博文《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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @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

1
2
3
4
5
6
7
8
9
10
11
12
/**
* @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);

二叉树版打家劫舍

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

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

为了表述题意,我们来看个例子吧:

1
2
3
4
5
3
/ \
2 3
\ \
3 1

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

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

LeetCode/337-rob3.js

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
/**
* 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,所以我们可以通过子节点的返回值(这里用 leftright来表示)得到当前节点的返回值,直到节点为空,就把递归终结掉!编写完了 dfs,我们对 root 入口进行 dfs,得到的数组就是“打劫根节点”和“不打劫根节点”的数值。最后,返回较大者即可得到答案。

测试代码如下:

LeetCode/__tests__/337-rob3.test.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
});

这里使用了前面编写的数据结构 BinarySearchTree,它的实现代码和具体讲解可以参考前面的博文《JavaScript 版数据结构与算法(七)树》

至此,“打家劫舍问题”就讲完了!其实,“打家劫舍问题”的本质在于使用“动态规划”,而“动态规划”的本质在于将大问题分解为相互依赖的子问题。看清问题本质,才能练好算法!加油吧!

教程示例代码及目录

示例代码:https://github.com/lewis617/javascript-datastructures-algorithms

目录:http://www.liuyiqi.cn/tags/数据结构与算法/