LeetCode题解——198. 打家劫舍

题目相关

题目链接

LeetCode中国，https://leetcode-cn.com/problems/house-robber/。

题目描述

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

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

示例

示例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 。

数据范围

0 <= nums.length <= 100
0 <= nums[i] <= 400

题目分析

LeetCode 给出本题难度简单。一个非常经典的动态规划问题，具体来说，属于时间序列动态规划范围。

本题的核心在于不能抢劫连续的两个房子。因此本题可以设计为两个状态，也就是对第 i 幢房子，我们将有两个状态，一个状态表示抢劫这个房子，一个状态表示不抢劫这个房子。因此，我们可以使用一个二维 DP 数组来表示，dp[i][0] 表示抢劫第 i 幢房子的最大收益，dp[i][1] 表示不抢劫第 i 幢房子的最大收益。

对于第 i 幢房子，我们有两个选择：抢劫第 i 幢房子；不抢劫第 i 幢房子。这样，我们可以绘制出如下的状态转移图，注意题目没有规定连续两个房子必须抢劫其中之一，说明我们可以不抢劫连续两个房子。

这样，我们可以推导出状态转移方程如下：

dp[i][0] = dp[i-1][1] + val[i]; //我们抢劫第 i 幢房子，这样能获得的收益： dp[i-1][1]（不抢劫第 i-1 幢房子的收益）加上第 i 幢房子的价值

dp[i][1] = max(dp[i-1][0], dp[i-1][1]); //我们不抢劫第 i 幢房子，这样能获得的收益：dp[i-1][0] 和 dp[i-1][1] 的最大值

这样本题就变成遍历所有房子，最终选取 dp[n-1][0] 和 dp[n-1][1] 的最大值，n 表示房子数量。

样例数据 1 分析

根据样例数据 1，我们知道房子的价值为 [1, 2, 3, 1]。

第 1 幢房子

抢劫第 1 幢房子，那么能获得的价值为 val[0]，也就是 dp[0][0]=1。

不抢劫第 1 幢房子，那么能获得的价值为 0，也就是 dp[0][1]=0。

第 2 幢房子

抢劫第 2 幢房子，那么能获得的价值为 val[1]，也就是 dp[1][0]=dp[0][1]+val[1]=0+2=2。

不抢劫第 2 幢房子，那么能获得的价值为 0，也就是 dp[1][1]=max(dp[0][0], dp[0][1])=1。

第 3 幢房子

抢劫第 3 幢房子，那么能获得的价值为 val[2]，也就是 dp[2][0]=dp[1][1]+val[2]=1+3=4。

不抢劫第 3 幢房子，那么能获得的价值为 0，也就是 dp[2][1]=max(dp[1][0], dp[1][1])=2。

第 4 幢房子

抢劫第 4 幢房子，那么能获得的价值为 val[3]，也就是 dp[3][0]=dp[2][1]+val[3]=2+1=3。

不抢劫第 4 幢房子，那么能获得的价值为 0，也就是 dp[3][1]=max(dp[2][0], dp[2][1])=4。

最终答案

最终答案为 max(dp[3][0], dp[3][1])=4。

样例数据 2 分析

根据样例数据 2，我们知道房子的价值为 [2, 7, 9, 3, 1]。

第 1 幢房子

抢劫第 1 幢房子，那么能获得的价值为 val[0]，也就是 dp[0][0]=2。

不抢劫第 1 幢房子，那么能获得的价值为 0，也就是 dp[0][1]=0。

第 2 幢房子

抢劫第 2 幢房子，那么能获得的价值为 val[1]，也就是 dp[1][0]=dp[0][1]+val[1]=0+7=7。

不抢劫第 2 幢房子，那么能获得的价值为 0，也就是 dp[1][1]=max(dp[0][0], dp[0][1])=2。

第 3 幢房子

抢劫第 3 幢房子，那么能获得的价值为 val[2]，也就是 dp[2][0]=dp[1][1]+val[2]=2+9=11。

不抢劫第 3 幢房子，那么能获得的价值为 0，也就是 dp[2][1]=max(dp[1][0], dp[1][1])=7。

第 4 幢房子

抢劫第 4 幢房子，那么能获得的价值为 val[3]，也就是 dp[3][0]=dp[2][1]+val[3]=7+3=10。

不抢劫第 4 幢房子，那么能获得的价值为 0，也就是 dp[3][1]=max(dp[2][0], dp[2][1])=11。

第 5 幢房子

抢劫第 5 幢房子，那么能获得的价值为 val[4]，也就是 dp[4][0]=dp[3][1]+val[4]=11+1=12。

不抢劫第 5 幢房子，那么能获得的价值为 0，也就是 dp[4][1]=max(dp[3][0], dp[3][1])=11。

最终答案

最终答案为 max(dp[4][0], dp[4][1])=12。

AC 参考代码

class Solution {
public:    
    int rob(vector<int>& nums) {
        int size=nums.size();
        if (0==size) {
            return 0;
        }

        //动态规划
        int dp[104][2] = {};
        //dp[i][0]表示我抢劫第 i 个房子
        //dp[i][1]表示不抢劫第 i 个房子
        dp[0][0]=nums[0];
        dp[0][1]=0;
        for (int i=1; i<size; i++) {
            dp[i][0]=dp[i-1][1]+nums[i];
            dp[i][1]=max(dp[i-1][0], dp[i-1][1]);
        }

        return max(dp[size-1][0], dp[size-1][1]);
    }
};