2020-07-02-PHP 动态规划计算打家劫舍问题

layout: posttitle: PHP 动态规划实现打家劫舍问题
subtitle: PHP 动态规划实现打家劫舍问题
date: 2020-07-02
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 打家劫舍问题
- 动态规划
- DP
- 按摩师问题

打家劫舍 Ⅰ

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber

解题思路

请参见 Sweetiee 发布的题解

php 代码 - 基础版的动态规划代码

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $count = count($nums);
        // 特殊数据特殊处理
        if ($count === 0) {
            return 0;
        }
        if ($count === 1) {
            return $nums[0];
        }
        // 定义和找到状态转移公式
        $dp = [];
        $dp[0] = $nums[0];
        $dp[1] = max($nums[0], $nums[1]);
        for ($i = 2; $i < $count; $i++) {
            $dp[$i] = max($dp[$i - 1], $dp[$i - 2] + $nums[$i]);
        }
        return $dp[$count - 1];
    }
}

还是参照着 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) 这个方程来写，

用 $last 表示 i - 2，$now 表示 i - 1，

因此上面的方程变成了 dp[i] = max(b, a + nums[i])，

然后下一轮循环的时候：
i - 1 就变成了 i - 2，因此现在需要把 $last 赋值给 $now；
i 就变成了 i - 1，因此现在需要把 dp[i] 赋值给 $last。

php 代码 - 精简版的动态规划代码

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $last = 0;
        $now = 0;
        foreach ($nums as $num) {
            $temp = $now;
            $now = max($last + $num, $now);
            $last = $temp;
        }
        return $now;
    }
}

此题和 按摩师 问题是一样的

打家劫舍 Ⅱ

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii

解题思路

doRob 函数主体结构一点没变，变化的是需要比较了，一共有三种偷法：① 首尾房子都不偷 ② 偷首不偷尾 ③ 偷尾不偷首，明显的 ② ③ 方案好，能多偷一个比少偷一个好，那就选择数组中的第二三方案的数据，然后计算最多能偷多少，比较两个偷法的结果，最大的那个就是。

PHP 代码

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $count = count($nums);
        if ($count === 1) {
            return $nums[0];
        }
        // array_slice 来截取 ② ③ 方案的数组数据
        return max($this->doRob(array_slice($nums, 0, $count - 1)), $this->doRob(array_slice($nums, 1, $count - 1)));
    }
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function doRob($nums) {
        $last = 0;
        $now = 0;
        foreach ($nums as $num) {
            $temp = $now;
            $now = max($last + $num, $now);
            $last = $temp;
        }
        return $now;
    }
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券