leetCode ✏Leetcode之PHP版题目解析（213. House Robber II）
✏描述
这是强盗第二版。就是说去抢劫，这是一组环形的房子，对应的数组上的数字代表对应房子可以偷的金额，有一个规则就是不能偷紧挨着的房子，比如example1中 你偷了2就不能接着偷3，这道题和198不同的地方在于，最后一个房子紧挨着第一座，所有成环。最终求你可以偷最大的钱，所以图1你忙一晚上只偷了三块，只偷了第二座
✏题目实例
✏题目分析
大体的解题和198那道题一样，采取动态规划。只是这里需要分为两个步骤，也就是第一座和最后一座偷了其中一个就不能偷另一座的特殊处理。另外定义两个变量分别用来存储奇位数($base)和偶位数($even)的值，如果遍历到偶数位就拿$even+当前的值和$base比较最大值，更新$even,如果是奇数位就相反。并不是说最后取得都是奇数或者偶数上的数，只是说每一步都更新奇数或者偶数为当前全局可以偷的最大值这样看有点绕，举个例子。
/**
* @param Integer[] $nums
* @return Integer
*/
function rob($nums) {
if(empty($nums)) return 0;
if(count($nums)==1) return $nums[0];
return max($this->helper($nums,0,count($nums)-1),
$this->helper($nums,1,count($nums)));
}
function helper($nums,$start,$end)
{
$even=0;
$base=0;
for($i=$start;$i<$end;$i++){
if($i % 2==0){
$even=max($even+$nums[$i],$base);
}else{
$base=max($base+$nums[$i],$even);
}
}
return max($even,$base);
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)