Leetcode基础刷题之PHP解析(198. House Robber Easy)

2019-4-11 星期四  开始吧

上一题链接Leetcode基础刷题之PHP解析(150. Evaluate Reverse Polish Notation)

题目描述

这是一道和盗窃有关的题目,挺有意思的.大致是说,数组中的每一个数代表着每栋房子的钱,小偷可以随意偷哪栋房子,但是如果相邻的房子被偷的话,那么就会触发报警器,也就是求在不触发报警器的情况下最多能偷多少钱.

题目分析

像求最优,最大,最小,最长....通常都可以利用动态规划,可以是把大问题化成相同的小问题的递归式.或者是自底向上一直推.先来看一种解法.由于每次偷的房子要么是奇数位的要么是偶数位的,所以我可以定义两个变量分别代表着偶数位和奇数位的金钱,如果是偶数位的话就把存偶数位的钱加上当前偶数位房子的钱,和存奇数位的钱相比较,取最大的值来更新偶数位的钱,反之如果是奇数位也一样.总结就是不管偷到哪座房子,都要保证当前偷的是最多的.还需要注意的是,并不是说最后抢劫的房子都是奇数位或者都是偶数位.我列了一个例子.

具体实现

   /**
     * @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];
    }

 github地址:https://github.com/wuqinqiang/leetcode-php