213. House Robber II
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
这个题目是基于House Robber I 的，所以做这题之前要先知道HouseRobber I的解法。
House Robber I 的传送门:
如果已经ac了第一题，那么这题的意思就是把屋子都改成环状。
在第一题中，dp状态转移方程 max[ i ] = Math.max( max[ i - 1 ], nums[ i - 1 ] + max[ i - 2 ] ) 已经做出来了。那么第二题就很好做了。
第二题中，我的做法就是要再进行一次dp，并且需要记录下选择屋子的首尾，记为start和last.
在记录start的时候，要注意start的状态 : 1.当前面的屋子已经被选择。2.当前面的屋子没有被选择。
所以这里的dp转移方程总结为:
if( max[ i - 1 ] > nums[ i - 1 ] + max[ i - 2 ] ) {
max[ i ] = max[ i - 1 ];
start[ i ] = start[ i - 1 ];
} else {
max[ i ] = nums[ i - 1 ] + max[ i - 2 ];
last = i;
if( max[ i - 1 ] == max[ i - 2 ] ) {
start[ i ] = start[ i - 2 ];
} else {
start[ i ] = start[ i - 2 ] == 0 ? 2 : start[ i - 2 ];
}
}
最后判断一下，如果是选择最后一个的时候报警了，进行判断是要选择(1,n)还是(0,n-1)的最大价值
总的思想就是进行两次DP，(1,n)和(0,n-1)分别Dp
Ps:暂时没有想到更好更加简洁的方法。不过我觉得是有的，只是本人愚笨没想到
public class Solution {
public int rob( int[] nums ) {
int[] max = new int[ nums.length + 1 ];
int[] start = new int[ nums.length + 1 ];
max[ 0 ] = 0;
start[ 0 ] = 0;
if( nums == null || nums.length == 0 )
return 0;
max[ 1 ] = nums[ 0 ];
start[ 1 ] = 1;
int last = 1;
for( int i = 2; i <= nums.length; i++ ) {
if( max[ i - 1 ] > nums[ i - 1 ] + max[ i - 2 ] ) {
max[ i ] = max[ i - 1 ];
start[ i ] = start[ i - 1 ];
} else {
max[ i ] = nums[ i - 1 ] + max[ i - 2 ];
last = i;
if( max[ i - 1 ] == max[ i - 2 ] ) {
start[ i ] = start[ i - 2 ];
} else {
start[ i ] = start[ i - 2 ] == 0 ? 2 : start[ i - 2 ];
}
}
}
if( ( last + 1 ) % nums.length == start[ nums.length ] ) {
int[] tail = new int[nums.length-1];
System.arraycopy( nums, 1, tail, 0, nums.length-1 );
int preMax = rob2( tail );
max[ nums.length ] = Math.max( ( max[ nums.length ] - max[ 1 ] ), max[ nums.length - 1 ] );
max[ nums.length ] = Math.max( max[ nums.length ], preMax );
}
return max[ nums.length ];
}
public int rob2( int[] nums ) {
int[] max = new int[ nums.length + 1 ];
max[ 0 ] = 0;
if( nums == null || nums.length == 0 )
return 0;
max[ 1 ] = nums[ 0 ];
for( int i = 2; i <= nums.length; i++ ) {
max[ i ] = Math.max( max[ i - 1 ], nums[ i - 1 ] + max[ i - 2 ] );
}
return max[ nums.length ];
}
public static void main( String[] args ) {
Solution s = new Solution();
int[] nums = new int[] { 2, 2, 4, 3, 2, 5 };
System.out.println( s.rob( nums ) );
}
}