代码随想录算法训练营第四十八天| 198.打家劫舍、213.打家劫舍II、337.打家劫舍III

文章目录

      • 198.打家劫舍
      • 213.打家劫舍II
      • 337.打家劫舍III

198.打家劫舍

  • 题目链接:代码随想录

  • 解题思路:
    1.dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i] 只是考虑,不一定偷
    2.递推公式:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]),根据选不选i位置,由两个方面推导而来
    3.dp数组如何初始化。因为递推公式是dp[i-1]和dp[i-2],所以初始化要考虑dp[0]和dp[1]
    因为要取最大值,所以dp[0] 一定是 nums[0],dp[1]就是nums[0]和nums[1]的最大值即:dp[1] = max(nums[0], nums[1])
    4.遍历顺序:从前向后。因为后面状态由前面推出来

public int rob(int[] nums) {

    if(nums.length == 1){
        return nums[0];
    }

    //1.定义dp数组,dp数组表示dp[i],考虑i位置的情况下能打劫到的最大价值
    //这里dp[i]中的i代表不一定选第i个位置的数字
    int[] dp = new int[nums.length];

    //2.初始化
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    //3.遍历
    for (int i = 2; i < dp.length; i++) {
        //根据选不选i位置的数值
        //选,只能加上dp[i-2]的数值
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }

    //4.最后返回递推的结果
    return dp[nums.length - 1];
}

213.打家劫舍II

关键点:将环形问题的情况分解成线性问题的情况,进而求解

  • 题目链接:代码随想录

  • 解题思路:
    ①根据环形问题,分为三种情况一种不考虑首尾,一种考虑首不考虑尾,最后一种考虑尾不考虑首
    后两种情况考虑首不考虑尾就包含了不考虑首尾的问题,因此只用将最后两种打家劫舍问题求一个和即可
    编写一个有参数的打家劫舍函数,里面进行初始化和相应范围的打家劫舍问题的分析。
    要想编写容易,要借用自动扩容的ArrayList数组,dp范围和nums范围和位置一致

  • 三种状态

    Snipaste_2023-05-01_21-51-56 Snipaste_2023-05-01_21-52-06 Snipaste_2023-05-01_21-52-22
public int rob(int[] nums) {
    int len = nums.length;
    //保证len从3开始
    if(len == 1){
        return nums[0];
    }
    if(len == 2){
        return Math.max(nums[0], nums[1]);
    }

    return Math.max(robAction(nums, 0, len - 2),robAction(nums, 1, len - 1));

}

/**
     * 考虑[start,end]位置房屋的打家劫舍问题
     * @param nums
     * @param start
     * @param end
     * @return
     */
private int robAction(int[] nums, int start, int end) {
    //定义dp数组的时候,要选用可扩容的ArrayList,因为要保证dp数组下标值和nums数组下标值一样
    List<Integer> dp = new ArrayList<>(nums.length);
    for(int i = 0;i < dp.size();i++){
        dp.add(0);
    }
    //初始化
    dp.set(start, nums[start]);
    dp.set(start + 1, Math.max(nums[start], nums[start + 1]));
    for (int i = start + 2; i <= end; i++) {
        dp.set(i, Math.max(dp.get(i - 2) + nums[i], dp.get(i - 1)));
    }

    return dp.get(end);
}
public static void main(String[] args) {
    List<Integer> dp = new ArrayList<>(2);
    System.out.println(dp.size());//0  这里只有首次添加元素之后,size1才变化
    dp.add(0, 0);
    System.out.println(dp.size());//1
}

337.打家劫舍III

本题是树形dp的入门级别的题目,通过返回dp数组来保存遍历状态 也称状态标记递归,通过一个标记,来记录遍历过程中的最大值

  • 题目链接:代码随想录

  • 解题思路:
    1.确定递归函数的参数和返回值
    那么返回值就是一个长度为2的dp数组。dp[0]表示不偷当前节点情况下的金钱dp[1]偷当前节点情况下的金钱,参数为当前节点,将当前节点偷与不偷得到的金钱返回给上一层
    在递归过程中,系统栈会保存每一层递归的参数,因此每一个节点的dp数组经过分析汇聚给root
    2.终止条件
    遇到空节点,直接返回本层偷的结果{0,0}
    3.确定遍历顺序:
    采用后序遍历,因为要根据左右节点的偷的金钱状态,根节点判断当前根偷还是不偷
    这种需要依靠状态的,都需要采取后序遍历
    4.确定单层递归逻辑:
    如果偷当前节点,那么dp[1] = root.val + 左右节点不偷的金钱
    如果不偷当前节点,那么左右节点可以偷,也可以不偷,因此dp[0] = max([0],[1])(左右节点)

  • 推导过程:

    Snipaste_2023-05-01_23-34-31
public int rob(TreeNode root) {
    int[] dp = robAction1(root);

    return Math.max(dp[0], dp[1]);
}


/**
     * 递归树
     * @param root
     * @return 一个dp一维数组
     */
private int[] robAction1(TreeNode root){
    //本层dp状态数组
    int[] dp = new int[2];
    //终止条件
    if(root == null){
        return dp;
    }

    int[] leftDp = robAction1(root.left);
    int[] rightDp = robAction1(root.right);

    //本根不偷
    dp[0] = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);
    //本根偷
    dp[1] = root.val + leftDp[0] + rightDp[0];

    //返回本层偷与不偷的状态
    return dp;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/17232.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

GPT-4等大语言模型对教育的未来意味着什么?

‍ ‍ shadow Mixlab这些年举办了非常多的活动和workshop&#xff0c;都带有很强的教育属性。今天我抽空学习了可汗学院的《AI-for-Education》课程&#xff0c;非常有启发。我记录了精华内容&#xff0c;分享给大家。 课程地址&#xff1a; www.khanacademy.org/college-caree…

设计模式——观察者模式

导航&#xff1a; 【黑马Java笔记踩坑汇总】JavaSEJavaWebSSMSpringBoot瑞吉外卖SpringCloud黑马旅游谷粒商城学成在线设计模式牛客面试题 目录 观察者模式 1、天气预报需求 2、天气预报需求方案之普通方案 3、观察者模式介绍 4、观察者模式优化天气预报案例 5、JDK 的O…

销售数据分析怎么做?这篇文章说清楚了

如何分析销售数据&#xff1f;分析销售数据有哪些指标&#xff1f;销售数据分析有什么作用&#xff1f; 销售数据是不是得通过数据分析软件啊&#xff1f; 本文将为您解答疑惑—— 一、分析销售数据的指标 从两个层面上来讲&#xff0c;一个是对销售情况的整体把控&#xf…

红黑树理论详解与Java实现

文章目录 基本定义五大性质红黑树和2-3-4树的关系红黑树和2-3-4树各结点对应关系添加结点到红黑树注意事项添加的所有情况 添加导致不平衡叔父节点不是红色节点&#xff08;祖父节点为红色&#xff09;添加不平衡LL/RR添加不平衡LR/RL 叔父节点是红色节点&#xff08;祖父节点为…

破解马赛克有多「容易」?

刷短视频时&#xff0c;估计大家都看过下面这类视频&#xff0c;各家营销号争相曝光「一分钟解码苹果笔刷背后内容」的秘密。换汤不换药&#xff0c;自媒体们戏称其为「破解马赛克」&#xff0c;殊不知让多少不明真相的用户建立起了错误的认知&#xff0c;也让苹果笔刷第 10086…

【面试】嵌入式C语言题目整理

【面试】嵌入式C语言题目整理 描述内存四区。 内存四区分为&#xff1a;代码区、静态区、堆区、栈区 代码区就是用来存放代码的。 静态区用来存放全局变量、静态变量、常量&#xff08;字符串常量、const修饰的全局变量&#xff09;。 堆区中的内存是由程序员自己申请和释放的&…

九、MyBatis动态SQL

文章目录 九、动态SQL9.1 if9.2 where9.3 trim9.4 choose、when、otherwise9.5 foreach9.6 SQL片段 本人其他相关文章链接 九、动态SQL 9.1 if 总结&#xff1a;根据标签中test属性所对应的表达式决定标签中的内容是否需要拼接到SQL中。 User getUserByParamsWithIf(User user…

Packet Tracer - 在思科路由器上配置 AAA 认证

Packet Tracer - 在思科路由器上配置 AAA 认证 拓扑图 地址分配表 设备 接口 IP 地址 子网掩码 默认网关 交换机端口 R1 G0/1 192.168.1.1 255.255.255.0 不适用 S1 F0/1 S0/0/0 (DCE) 10.1.1.2 255.255.255.252 不适用 不适用 R2 G0/0 192.168.2.1 255.2…

(四)Kubernetes - 手动部署(二进制方式安装)

Kubernetes - 手动部署 [ 3 ] 1 部署work node1.1 创建工作目录并拷贝二进制文件1.2 部署kubelet1.2.1 创建配置文件1.2.2 配置文件1.2.3 生成kubelet初次加入集群引导kubeconfig文件1.2.4 systemd管理kubelet1.2.5 启动并设置开机启动1.2.6 允许kubelet证书申请并加入集群 1.3…

JAVA-异常

文章目录 1.异常的体系1.3异常的分类 2.异常的处理2.2异常的抛出throw2.3异常的捕获2.3.1异常声明throws2.3.2 try-catch捕获并处理2.3.3 finally 2.4 异常的处理流程 3.自定义异常类 1.异常的体系 Throwable&#xff1a;是异常体系的顶层类&#xff0c;其派生出两个重要的子类…

人员拥挤检测系统 yolov5

人员拥挤检测系统通过YOLOv5网络模型算法技术&#xff0c;人员拥挤检测系统算法模型对校园/厂区车间/街道等场景的异常的人群聚集&#xff08;出现拥挤情况&#xff09;时&#xff0c;立刻抓拍存档并通知相关人员及时处理。在介绍Yolo算法之前&#xff0c;首先先介绍一下滑动窗…

ES是如何解决高可用

https://www.cnblogs.com/crazymakercircle/p/15433680.html ES是一个分布式全文检索框架&#xff0c;隐藏了复杂的处理机制&#xff0c;核心数据分片机制、集群发现、分片负载均衡请求路由。 ES的高可用架构&#xff0c;总体如下图&#xff1a; 说明&#xff1a;本文会以pdf…

Java 基础入门篇(一)—— Java 概述

文章目录 一、Java 概述二、Java 的产品 JDK2.1 JDK 安装2.2 Java与 Javac 介绍2.3 Java 程序的开发步骤 三、Java 程序的执行原理四、JDK 的组成五、Java 的跨平台工作原理 一、Java 概述 Java 是 sun 公司在 1995 年推出的一门计算机高级编程语言&#xff0c;其语言风格接近人…

深度学习卷积神经网络学习小结2

简介 经过大约两周左右的学习&#xff0c;对深度学习有了一个初步的了解&#xff0c;最近的任务主要是精读深度学习方向的文献&#xff0c;由于搭建caffe平台失败而且比较耗费时间就没有再尝试&#xff0c;所以并没有做实践方面的工作&#xff0c;本文只介绍了阅读文献学到的知…

外卖项目优化-02-mysql主从复制、读写分离(shardingJdbc)、Nginx(反向代理,负载均衡)

文章目录 瑞吉外卖项目优化-Day02课程内容前言1. MySQL主从复制1.1 介绍1.2 搭建1.2.1 准备工作1.2.2 主库配置1.2.3 从库配置 1.3 测试 2. 读写分离案例 (shardingJdbc)2.1 背景介绍2.2 ShardingJDBC介绍2.3 数据库环境2.4 初始工程导入2.5 读写分离配置2.6 测试 3. 项目实现读…

基于ATECLOUD的航电系统可灵活扩展自动化测试平台

随着电子技术的发展&#xff0c;航电系统在飞机整机中的重要性飞速提升。据统计&#xff0c;近年来航电系统在飞机出厂成本中的比例直线上升&#xff0c;航电系统研发成本已占飞机研制总成本的近30%&#xff0c;并保持着持续扩大的趋势。测试保障作为航电产业链至关重要的一环&…

基于JavaWeb实现的寻码网文章资讯管理系统

一、技术结构 前端&#xff1a;html ajax 后端&#xff1a;SpringBootMybatis-plus 环境&#xff1a;JDK1.8 | Mysql | Maven | Redis 二、功能简介 数据库与代码截图 后端管理-登录页 后端管理-首页 后端管理-文章管理-发布文章 后端管理-文章管理-文章列表 后端管理-文…

【iOS KVO(下) KVO的内部结构和源码】

前言 学习KVO的过程&#xff0c;我分为了KVO的实现过程分析和内部结构的学习&#xff0c;学习了实现过程&#xff0c;接下来看KVO是通过何种内部结构实现如此通知&#x1f4e2;和监听。 1 KVO的存储结构 KVO的实现过程离不开合理的存储结构&#xff0c;用到了如下几个类 GS…

智能安防系统-视频监控系统

一、智能安防系统 1、智能安防系统介绍 安全防范系统成为了智慧城市与物联网行业应用中的一个非常重要的子系统。 安防系统主要包括&#xff1a;视频监控系统、入侵报警系统、出入口控制系统、电子巡查系统以及智能停车场管理系统等5个子系统。 AI人工智能安防系统功能&#xf…

Java8中DateTimeFormatter真的是线程安全的吗?

文章目录 [toc] 1.背景2.解决办法2.1办法一&#xff1a;换姿势或者升级JDK的版本2.1办法二&#xff1a;更换文件名称字生成策略 Java8中DateTimeFormatter真的是线程安全的吗&#xff1f; 答案是否定的 1.背景 由于之前写了一个旷世的ocr的服务,接入了旷世的FaceID的人脸比对…
最新文章