forked from reedfan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathN198Rob.java
More file actions
72 lines (55 loc) · 1.53 KB
/
Copy pathN198Rob.java
File metadata and controls
72 lines (55 loc) · 1.53 KB
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
package leetcode.dp;
public class N198Rob {
public static void main(String[] args) {
int[] nums = {1,2,3,1,5,4,6};
System.out.println(new N198Rob().rob(nums));
System.out.println(new N198Rob().robdigui(nums,nums.length-1));
System.out.println(new N198Rob().robdp(nums));
}
//递归解法
public int robdigui(int[] nums,int index) {
if(index == 0){
return nums[0];
}
if(index == 1){
return Math.max(nums[0],nums[1]);
}
return Math.max(robdigui(nums,index-1),robdigui(nums,index-2)+nums[index]);
}
//动态规划解法
public int rob(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int len = nums.length;
if(len == 1){
return nums[0];
}
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i = 2;i< len;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[len-1];
}
//动态规划解法的空间压缩
public int robdp(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int len = nums.length;
if(len == 1){
return nums[0];
}
int a = nums[0];
int b = Math.max(nums[0],nums[1]);
int c = 0;
for(int i = 2;i< len;i++){
c = Math.max(b,a+nums[i]);
a = b;
b = c;
}
return c;
}
}