Leetcode 简单十四 198.打家劫舍

打家劫舍：

 

动态规划：

php，8ms。

状态转移方程：

$dp[$i] = max($dp[$i-2]+$nums[$i],$dp[$i-1]);

• 情况一，当前这一家的钱不能偷，最大的就是截止到上一家偷到的总金额
• 情况二，当前可以偷，那就是上上家偷到的总金额加上这家的钱nums[i]

ps :题目没有说明只能隔一家，所以只计算奇数和偶数是错误的。

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        if(empty($nums)) return 0;
        if(count($nums) == 1) return $nums[0];
        $dp = [];
        $dp[0] = $nums[0];
        $dp[1] = max($nums[1],$nums[0]);
        for($i = 2;$i < count($nums);$i++){
            $dp[$i] = max($dp[$i-2]+$nums[$i],$dp[$i-1]);
        }
        return max($dp);
    }
}