Visits: 139

LeetCode 198 打家劫舍

题目描述

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

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

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

样例

样例输入1

[1,2,3,1]

样例输出1

4

样例解释1：

偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

样例输入2

[2,7,9,3,1]

样例输出2

12

样例解释2：

偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

算法与数据结构

动态规划

题解

动态规划一直是算法中的一个难点，今天开始的一段时间内本长老会陆续更新一些动态规划的专题，由简单到困难，跟着长老一起学习动态规划吧！

今天先来一道题目热热身。

由题目可知，我们需要在给定的数组中寻找若干个数，使得这些数的总和最大，但是要求不能选择相邻的数。

遍历一遍所有的情况，那么长度为 $n$ 的数组就会有 $2^n$ 种可能的选择，求出所有选择中最大的和，这会非常浪费时间。

定义 dp[i] 表示到第 i 个房间为止，小偷能偷到的最大金额。

显然，从 j = 0 到 j = i – 1 为止，dp[j] 的值都已经知道了，那么，如何确定 dp[i]？

小偷面对第 i 间房间，有 2 个选择：

1. 如果前一个房间已经进去过，那么这个房间显然不能进去，否则会触发警报，此时 dp[i] = dp[i - 1]；
2. 如果前一个房间没有进去过，那么这个房间可以进去看看，此时 dp[i] = dp[i - 2] + nums[i]。

只需要保留上面两种情况中较大的一个就可以了，因此，可以顺利得到递推公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

可以看到，dp[i] 仅仅依赖于有限个 dp[j]，其中 j = i – 1 和 i – 2。因此，对于 dp[] 数组的初始化，需要特别处理 dp[0] 和 dp[1] 的值。对于 i = 0 的情况，显然 dp[0] = nums[0]，对于 i = 1 的情况，则应该是 nums[0] 和 nums[1] 中较大的一者，相当于小偷在第 0 和第 1 间房间中选择了更有钱的那一个。

int dp[k] = {0};
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

从 i = 2 开始，运用递推公式得到各个结果，最后 dp[n - 1] 就是答案。

for (int i = 2; i < k; i++) {
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}

由于上面的初始化中，我们显式地使用了 nums[0] 和 nums[1]，因此，若 nums[] 长度小于 2 时，要进行特殊处理。

const int k = nums.size();
int ans = 0;
if (k == 0) {
    ans = 0;
} else if (k == 1) {
    ans = nums[0];
} else {
    // TODO
}

完整代码

int rob(vector<int>& nums) {
    const int k = nums.size();
    int ans = 0;
    if (k == 0) {
        ans = 0;
    } else if (k == 1) {
        ans = nums[0];
    } else {
        int dp[k] = {0};

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < k; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        ans = dp[k - 1];
    }
    return ans;
}