-
Notifications
You must be signed in to change notification settings - Fork 11
/
213.打家劫舍-ii.java
42 lines (38 loc) · 956 Bytes
/
213.打家劫舍-ii.java
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
/*
* @lc app=leetcode.cn id=213 lang=java
*
* [213] 打家劫舍 II
*/
// @lc code=start
import java.util.*;
class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length ==0){
return 0;
}
int len = nums.length;
if(len == 1){
return nums[0];
}
int[] one = Arrays.copyOfRange(nums,0,len-1);
int[] two = Arrays.copyOfRange(nums,1,len);
return Math.max(countRob(one),countRob(two));
}
public int countRob(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-2]+nums[i],dp[i-1]);
}
return dp[len-1];
}
}
// @lc code=end