forked from DreamCats/java-notes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathT3.java
More file actions
33 lines (31 loc) · 927 Bytes
/
Copy pathT3.java
File metadata and controls
33 lines (31 loc) · 927 Bytes
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
/**
* @program JavaBooks
* @description: 打家劫舍
* @author: mf
* @create: 2020/04/14 15:29
*/
package subject.dp;
/**
* 输入: [1,2,3,1]
* 输出: 4
* 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
* 偷窃到的最高金额 = 1 + 3 = 4 。
* 输入: [2,7,9,3,1]
* 输出: 12
* 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
* 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
*/
public class T3 {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int pre3 = 0, pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
int cur = Math.max(pre3, pre2) + nums[i];
pre3 = pre2;
pre2 = pre1;
pre1 = cur;
}
return Math.max(pre2, pre1);
}
}