友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.Example 2:
Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.思路分析
假设 f(k) = 从前 k 个房屋中能抢劫到的最大数额，Ai = 第 i 个房屋的钱数。
当 n=1 时，显然 f(1) = A1。
当 n=2 时，f(2) = max(A1, A2)。
当 n=3 时，有两种选项：
-
将第三个房间金额和第一个房间金额相加；
-
不算第三个房间，保持当前最大金额。
于是，可以总结出公式: \(f(k)=\max \left(f(k-2)+A_{k}, f(k-1)\right)\)。
剩下的工作就好办了。
让 D瓜哥 使用 动态规划的模式 来重新解读一下：
-
刻画一个最优解的结构特征：求解抢劫金额最大值。
-
递归地定义最优解的值： \(f(k)=\max \left(f(k-2)+A_{k}, f(k-1)\right)\)。
-
计算最优解的值，通常采用自底向上的方法：D瓜哥也按照动态规划（注意表格）的方式来实现，采用自底向上+备忘录的方式来求解，创建一个长度为 n+1 的数组，第 i 个元素表示到第 i 个房间为止，最大抢劫金额；则第 0 个元素为 0，第 1 个元素为 A1。然后根据上述公式定义，以此类推……
-
利用计算出的信息构造一个最优解。这一步不需要，暂时忽略。
使用递归、递归+备忘录、自底向上+备忘录，自底向上+简化备忘录四种方式分别实现。
-
一刷
-
二刷
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber.
*
* Memory Usage: 41.2 MB, less than 5.26% of Java online submissions for House Robber.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-23 22:37
*/
public int rob(int[] nums) {
int k2 = 0;
int k1 = 0;
for (int num : nums) {
int current = Math.max(k2 + num, k1);
k2 = k1;
k1 = current;
}
return k1;
}
/**
* Runtime: 1 ms, faster than 5.81% of Java online submissions for House Robber.
*
* Memory Usage: 41.9 MB, less than 5.26% of Java online submissions for House Robber.
*/
public int robDP(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
int[] memo = new int[nums.length + 1];
memo[0] = 0;
memo[1] = nums[0];
for (int i = 2; i < memo.length; i++) {
int max = Math.max(memo[i - 2] + nums[i - 1], memo[i - 1]);
memo[i] = max;
}
return memo[nums.length];
}
/**
* Runtime: 1 ms, faster than 5.81% of Java online submissions for House Robber.
*
* Memory Usage: 41.3 MB, less than 5.26% of Java online submissions for House Robber.
*/
public int robRecursionWithMemo(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return 0;
}
int[] memo = new int[nums.length];
Arrays.fill(memo, Integer.MIN_VALUE);
memo[0] = nums[0];
rob(nums, memo, nums.length - 1);
return memo[nums.length - 1];
}
private int rob(int[] nums, int[] memo, int k) {
if (k == -2 || k == -1) {
return 0;
}
int rob2 = 0;
if (k - 2 >= 0 && memo[k - 2] >= 0) {
rob2 = memo[k - 2];
} else {
rob2 = rob(nums, memo, k - 2);
}
int rob1 = 0;
if (k - 1 >= 0 && memo[k - 1] >= 0) {
rob1 = memo[k - 1];
} else {
rob1 = rob(nums, memo, k - 1);
}
int rob0 = Math.max(rob2 + nums[k], rob1);
memo[k] = rob0;
return rob0;
}
// -----
public int robRecursion(int[] nums) {
return rob(nums, nums.length - 1);
}
private int rob(int[] nums, int k) {
if (k == -2 || k == -1) {
return 0;
}
return Math.max(rob(nums, k - 2) + nums[k], rob(nums, k - 1));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-23 22:37
*/
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
// 1. 确定 dp 数组（dp table）以及下标的含义
int[] dp = new int[nums.length];
// 3. dp 数组如何初始化
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// 4. 确定遍历顺序
for (int i = 2; i < nums.length; i++) {
// 2. 确定递推公式: max(dp[i-3]+nums[i], dp[i-2]+nums[i], dp[i-1])
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}