|
3 | 3 | publicclass_213 { |
4 | 4 | publicstaticclassSolution1 { |
5 | 5 | /** |
6 | | - * Another dp problem: |
7 | | - * separate them into two cases: |
8 | | - * 1. rob from house 1 to n-1, get max1 |
9 | | - * 2. rob from house 2 to n, get max2 take the max from the above two max |
| 6 | + * Basically there are two ways to rob the houses: one is to rob from 0 to n - 1, the other is to rob from 1 to n, and then take the max from these two. |
| 7 | + * Time: O(n) |
| 8 | + * Space: O(n) |
10 | 9 | */ |
11 | 10 | publicintrob(int[]nums) { |
12 | | -if (nums ==null ||nums.length ==0) { |
13 | | -return0; |
14 | | - } |
15 | 11 | if (nums.length ==1) { |
16 | 12 | returnnums[0]; |
17 | 13 | } |
18 | | -if (nums.length ==2) { |
19 | | -returnMath.max(nums[0],nums[1]); |
20 | | - } |
21 | | -int[]dp =newint[nums.length -1]; |
| 14 | +returnMath.max(rob(nums,0,nums.length -1),rob(nums,1,nums.length)); |
| 15 | + } |
22 | 16 |
|
23 | | -//rob 1 to n-1 |
24 | | -dp[0] =nums[0]; |
25 | | -dp[1] =Math.max(nums[0],nums[1]); |
26 | | -for (inti =2;i <nums.length -1;i++) { |
| 17 | +privateintrob(int[]nums,intstart,intend) { |
| 18 | +int[]dp =newint[nums.length]; |
| 19 | +dp[start] =nums[start]; |
| 20 | +if (end -start <=1) { |
| 21 | +returnnums[start]; |
| 22 | + } |
| 23 | +dp[start +1] =Math.max(nums[start],nums[start +1]); |
| 24 | +for (inti =start +2;i <end;i++) { |
27 | 25 | dp[i] =Math.max(dp[i -2] +nums[i],dp[i -1]); |
28 | 26 | } |
29 | | -intprevMax =dp[nums.length -2]; |
| 27 | +returndp[end -1]; |
| 28 | + } |
| 29 | + } |
30 | 30 |
|
31 | | -//rob 2 to n |
32 | | -dp =newint[nums.length -1]; |
33 | | -dp[0] =nums[1]; |
34 | | -dp[1] =Math.max(nums[1],nums[2]); |
35 | | -for (inti =3;i <nums.length;i++) { |
36 | | -dp[i -1] =Math.max(dp[i -3] +nums[i],dp[i -2]); |
| 31 | +publicstaticclassSolution2 { |
| 32 | +/** |
| 33 | + * This solution is identical to the above solution 1, the only difference is that instead of using an extra array, we use only two extra variables here to reduce the space complexity to O(1). |
| 34 | + * Time: O(n) |
| 35 | + * Space: O(1) |
| 36 | + * <p> |
| 37 | + * Just draw out how this rotation works on a piece of paper, it'll be easy to figure out how first, second and tmp variables keep shifting towards the right of the array. |
| 38 | + */ |
| 39 | +publicintrob(int[]nums) { |
| 40 | +if (nums.length ==1) { |
| 41 | +returnnums[0]; |
| 42 | + } |
| 43 | +returnMath.max(rob(nums,0,nums.length -1),rob(nums,1,nums.length)); |
| 44 | + } |
| 45 | + |
| 46 | +privateintrob(int[]nums,intstart,intend) { |
| 47 | +intfirst =nums[start]; |
| 48 | +if (end -start <=1) { |
| 49 | +returnfirst; |
| 50 | + } |
| 51 | +intsecond =Math.max(nums[start],nums[start +1]); |
| 52 | +inttmp; |
| 53 | +for (inti =start +2;i <end;i++) { |
| 54 | +tmp =Math.max(second,first +nums[i]); |
| 55 | +first =second; |
| 56 | +second =tmp; |
37 | 57 | } |
38 | | -returnMath.max(prevMax,dp[nums.length -2]); |
| 58 | +returnMath.max(first,second); |
39 | 59 | } |
40 | 60 | } |
41 | 61 | } |