动态规划之打家劫舍

简介: 动态规划之打家劫舍

四、打家劫舍


打家劫舍(LeetCode-198)

题目

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


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


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


提示:


1 <= nums.length <= 100

0 <= nums[i] <= 400


思路

五部曲


dp[i]含义


偷窃前 i 个房子(包括房子i)可以获取的最大金额

递推公式


d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] )


数组初始化


dp[0]=0 dp[1]=nums[0]

遍历顺序


从前往后


代码

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        if (n == 2)
        {
            return max(nums[0], nums[1]);
        }
        vector<int> dp(2);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        int result;
        for (int i = 2; i < n; i++)
        {
            result = max(dp[1], dp[0] + nums[i]);
            dp[0] = dp[1];
            dp[1] = result;
        }
        return result;
    }
};


打家劫舍Ⅱ(LeetCode-213)

题目

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


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


示例 1:

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


示例 2:

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


示例 3:

输入:nums = [1,2,3]
输出:3


提示:


1 <= nums.length <= 100

0 <= nums[i] <= 1000


思路

当房间数不超过二,不需要考虑首尾


超过二时,因为不能同时偷首尾房间,所以可以分两种情况考虑


不偷最后一间情况:盗窃范围 n u m s [ 0 : n − 2 ] nums[0:n-2]nums[0:n−2]

不偷第一间情况:盗窃范围 n u m s [ 1 : n − 1 ] nums[1:n-1]nums[1:n−1]

二者取较大值


代码展示

class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
        {
            return nums[0];
        }
        int left = robRange(nums, 0, n - 2);
        int right = robRange(nums, 1, n - 1);
        return max(left, right);
    }
    int robRange(vector<int> &nums, int start, int end)
    {
        if (start == end)
        {
            return nums[start];
        }
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
};


打家劫舍Ⅲ(LeetCode-337)

题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。


除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。


给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。


示例 1:



输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7


示例 2:



输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9


提示:


树的节点数在 [1, 104] 范围内

0 <= Node.val <= 104


思路

树形数组


确定递归函数参数与返回值


返回偷和不偷两种状态下获得的金钱。下标0表示不偷当前节点获得的最大金额,下标1表示偷当前节点获得的最大金额

确定终止条件


遇到空节点,肯定返回 { 0 , 0 }


必须后序遍历,因为要通过递归函数返回值后考虑

确定单层逻辑


如果偷当前节点


左右孩子不能偷,即左右孩子各取下标0的值相加

v a l 1 = c u r . v a l + l e f t [ 0 ] + r i g h t [ 0 ]

如果不偷当前节点


左右孩子可以考虑偷,但到底偷不偷还是要判断

v a l 2 = m a x ( l e f t [ 0 ] , l e f t [ 1 ] ) + m a x ( r i g h t [ 0 ] , r i g h t [ 1 ] )


测试用例



代码展示

class Solution
{
public:
    int rob(TreeNode *root)
    {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    vector<int> robTree(TreeNode *cur)
    {
        if (!cur)
        {
            return {0, 0};
        }
        vector<int> curleft = robTree(cur->left);
        vector<int> curright = robTree(cur->right);
        int val1 = cur->val + curleft[0] + curright[0];
        int val2 = max(curleft[0], curleft[1]) + max(curright[0], curright[1]);
        return {val2, val1};
    }
};
目录
相关文章
|
7月前
|
NoSQL Java API
Redisson分布式锁使用详解
通过以上内容,您可以全面了解如何在Java项目中使用Redisson实现分布式锁,并根据不同的业务需求选择合适的锁机制。
575 33
|
运维 监控 Ubuntu
一键启动日志魔法:揭秘ELK自动安装脚本的神秘面纱!
【8月更文挑战第9天】在数据驱动时代,高效处理日志至关重要。ELK Stack(Elasticsearch、Logstash、Kibana)是强大的日志分析工具,但其复杂的安装配置常让初学者望而却步。本文介绍如何编写ELK自动安装脚本,简化部署流程。脚本适用于Ubuntu系统,自动完成ELK下载、安装及基本配置,包括依赖项安装、服务启动及自启设置,极大降低了使用门槛,助力运维人员和开发者轻松构建日志分析平台。
364 6
ly~
|
12月前
|
传感器 存储 供应链
大数据在供应链管理中的具体应用案例
以下是大数据在供应链管理中的具体应用案例:沃尔玛通过整合内外部数据进行需求预测,提前调配应急物资;亚马逊利用大数据优化库存管理,提高周转率并降低成本;DHL通过传感器收集数据优化物流路线,提升运输效率。大数据的优势在于提高需求预测准确性、优化库存管理、提升物流效率、增强供应商管理和提高供应链可视性,从而实现全方位的供应链优化。
ly~
2846 2
|
安全 Java 应用服务中间件
如何在 Spring Boot 3.3 中实现请求 IP 白名单拦截功能
【8月更文挑战第30天】在构建Web应用时,确保应用的安全性是至关重要的。其中,对访问者的IP地址进行限制是一种常见的安全措施,特别是通过实施IP白名单策略,可以只允许特定的IP地址或IP段访问应用,从而有效防止未授权的访问。在Spring Boot 3.3中,我们可以通过多种方式实现这一功能,下面将详细介绍几种实用的方法。
852 1
|
API 开发者
触发式邮件邮箱API发送邮件的方法和步骤
触发式邮件API如Aoksend让开发者能基于特定事件自动发送邮件。选择邮箱提供商(如Aoksend、Mailgun、AWS SES),注册并获取API密钥,设置权限和验证。编写代码调用API(示例代码提供),并在用户注册、订单处理等事件触发时发送邮件,提升效率和准确性。
|
存储 JavaScript 前端开发
vue3获取本地的当前时间转化为年月日显示然后计算之后一周的时间
vue3获取本地的当前时间转化为年月日显示然后计算之后一周的时间
|
机器学习/深度学习 算法 搜索推荐
KNN算法(k近邻算法)原理及总结
KNN算法(k近邻算法)原理及总结
1064 0
|
存储 移动开发 编解码
Vue3(开发h5适配)
Vue3(开发h5适配)
286 0
Vue3(开发h5适配)
|
数据采集 小程序 定位技术
[笔记]微信小程序开发《三》框架基础:小程序生命周期、全局配置、页面配置。
[笔记]微信小程序开发《三》框架基础:小程序生命周期、全局配置、页面配置。
140 0