本文写于 2020年02月26日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

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;
}
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论