2019-04-11 吴亲库里 库里的深夜食堂
这是一道和盗窃有关的题目,挺有意思的.大致是说,数组中的每一个数代表着每栋房子的钱,小偷可以随意偷哪栋房子,但是如果相邻的房子被偷的话,那么就会触发报警器,也就是求在不触发报警器的情况下最多能偷多少钱.
像求最优,最大,最小,最长....通常都可以利用动态规划,可以是把大问题化成相同的小问题的递归式.或者是自底向上一直推.先来看一种解法.由于每次偷的房子要么是奇数位的要么是偶数位的,所以我可以定义两个变量分别代表着偶数位和奇数位的金钱,如果是偶数位的话就把存偶数位的钱加上当前偶数位房子的钱,和存奇数位的钱相比较,取最大的值来更新偶数位的钱,反之如果是奇数位也一样.总结就是不管偷到哪座房子,都要保证当前偷的是最多的.还需要注意的是,并不是说最后抢劫的房子都是奇数位或者都是偶数位.我列了一个例子.
/**
* @param Integer[] $nums
* @return Integer
*/
function rob($nums) {
$odd=0;
$even=0;
for($i=0;$i<count($nums);$i++) {
if($i%2==0){
$even=max($even+$nums[$i],$odd);
}else{
$odd=max($odd+$nums[$i],$even);
}
}
return max($even,$odd);
}我们可以自底向上的推,每到第i个位置,就把第i个能偷的最大的金额数表示出来,最后我们只要返回最后一个位置的最大的数即可.
/**
* @param Integer[] $nums
* @return Integer
*/
function rob($nums) {
if(empty($nums)){
return 0;
}
$price[0]=$nums[0];
$price[1]=$price[0]>$nums[1]?$price[0]:$nums[1];
for($i=2;$i<count($nums);$i++){
$price[$i]=max($price[$i-2]+$nums[$i],$price[$i-1]);
}
return $price[count($nums)-1];
}
