FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

leetcode/code/lc213.java at master · mJackie/leetcode · GitHub

38 lines (36 loc) · 1.14 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

package code;

import java.util.Arrays;

/*

* 213. House Robber II

* 题意：数组最大和，不能选取相邻的两个数。数组首尾是连着的

* 难度：Medium

* 分类：Dynamic Programming

* 思路：分别把第一个元素置0和最后一个元素置0，用lc198的解法

*

* Tips：lc198

*/

public class lc213 {

public int rob(int[] nums) { //分别把第一个元素置0和最后一个元素置0，用lc198的解法

if(nums.length == 0)

return 0;

if(nums.length == 1)

return nums[0];

int res1 = helper(Arrays.copyOf(nums, nums.length-1));

nums[0] = 0;

int res2 = helper(nums);

return Math.max(res1, res2);

}

public int helper(int[] nums) {

if(nums.length == 0)

return 0;

if(nums.length == 1)

return nums[0];

int[] dp = new int[nums.length];

dp[0] = nums[0];

dp[1] = Math.max(nums[0], nums[1]);

for (int i = 2; i < nums.length ; i++) {

dp[i] = Math.max((dp[i-2] + nums[i]),dp[i-1]); //dp[i] 表示以 0~i 的数组的结果

}

return dp[nums.length-1];

}

}

Back | FazBrowse Home | New Git URL