动态规划day09(打家劫舍,树形dp)

news/2024/2/25 14:13:59/文章来源:https://blog.csdn.net/weixin_47455684/article/details/135634950

目录

198.打家劫舍

看到题目的第一想法

看到代码随想录之后的想法

自己实现过程中遇到的困难

213.打家劫舍II

看到题目的第一想法

看到代码随想录之后的想法

自己实现过程中遇到的困难

337.打家劫舍 III(树形dp)

看到题目的第一想法

看到代码随想录之后的想法

自己实现过程中遇到的困难


198.打家劫舍

力扣题目链接(opens new window)

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

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

  • 示例 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
看到题目的第一想法

        dp[j]设置为能偷到的最高金额

        由于相邻的不能偷于是最高金额应该从j-2,j-3种去取

        dp[j] = nums[i]+math.Max(dp[j-2],dp[j-3]);

        最终返回dp[j]与dp[j-1]中的最大值

看到代码随想录之后的想法

        我的想法并没有完全按照dp数组的定义来写,不具备普适性

        代码随想录中,dp的定义为能偷到的最高金额

        则目标元素应该有两种选择

        1 偷目标元素 :若偷目标元素为dp[j-2]+nums[i]

        2 不偷目标元素:若不偷目标元素为dp[j-1]

       dp[j] = Math.max(dp[j-2]+nums[i],dp[j-1]);

自己实现过程中遇到的困难

        初始化时 dp[0] = nums[0]

                        dp[1] = Math.max(nums[0],nums[1]); 应该是取两者的最大值,才能保证偷到最多

                        我写成了dp[1] = nums[1]

class Solution {/*public int rob(int[] nums) {// 定义dp数组以及每个下标的含义// 到达dp[i] 能偷窃到的最高金额// 确定递归函数// dp[i] = nums[i]+Math.max(dp[i-2],dp[i-3]);// 确定遍历顺序// 从前往后// dp数组初始化// dp[0] = nums[0], dp[1] = nums[1] , dp[2] = nums[2]+nums[0] // dp3 = nums[i]+Math.max(dp[i-2],dp[i-3])// 举例推导dp数组int[] dp = new int[nums.length];if(nums.length==1){return nums[0];}if(nums.length==2){return Math.max(nums[0],nums[1]);}if(nums.length==3){return Math.max(nums[0]+nums[2],nums[1]);}dp[0] = nums[0];dp[1] = nums[1];dp[2] = nums[2] + nums[0];for(int i=3;i<nums.length;i++){dp[i] = nums[i]+Math.max(dp[i-2],dp[i-3]);}return Math.max(dp[nums.length-2],dp[nums.length-1]);}*///卡哥思路public int rob(int[] nums) {//我的方法没有遵循dp数组的定义,dp[i] 代表当前最高金额// 当前最高金额,如果偷当前nums[i] 则dp[i] = nums[i]+dp[i-2]// 如果不偷当前nums[i] 则为dp[i-1]// 定义dp数组以及每个下标的含义// 考虑下标i 能偷到的最高金额// 确定递归函数// 对于nums[i] 我们能考虑是偷还是不偷// 若偷i 则 dp[i] = nums[i]+dp[i-2]// 若不偷i 则 dp[i] = dp[i-1]// dp[i] = nums[i]+Math.max(dp[i-2],dp[i-3]);// 确定遍历顺序// 从前往后// dp数组初始化// dp[0] = nums[0], dp[1] = nums[1] , dp[2] = nums[2]+nums[0] // dp3 = nums[i]+Math.max(dp[i-2],dp[i-3])// 举例推导dp数组int[] dp = new int[nums.length];if(nums.length==1){return nums[0];}if(nums.length==2){return Math.max(nums[0],nums[1]);}dp[0] = nums[0];//这里应该是Math.max(nums[0],nums[1]);我之前直接写成nums[1] 是错误的dp[1] = Math.max(nums[0],nums[1]);for(int i=2;i<nums.length;i++){dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);}return dp[nums.length-1];}
}

213.打家劫舍II

力扣题目链接(opens new window)

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

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

示例 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 = [0]

  • 输出:0

看到题目的第一想法

        和打家劫舍1差不多,只是要考虑首尾

        先处理[0,nums[length-2]]

        再处理[1,nums[length-1]]

        返回两者的最大值

看到代码随想录之后的想法

        和我思路差不多

自己实现过程中遇到的困难

        初始化时 dp[0] = nums[0]

                        dp[1] = Math.max(nums[0],nums[1]); 应该是取两者的最大值,才能保证偷到最多

                        我写成了dp[1] = nums[1]

class Solution {public int rob(int[] nums) {// 确定dp以及每个下标的含义// 第一个房屋和最后一个是紧挨着的// 主要是没办法确定是否加上了第一个// 今晚能偷窃到的最高金额// 我的思路 ,两次dp 一次从第一个到倒数第二个// 一次从第二个到最后一个。// 确定递推函数// dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);// 确定遍历顺序// 从前往后// dp数组初始化// dp[0] = nums[0],dp[1]=Math.max(nums[0],nums[1]);// 举例推导dp数组int[] dp1 = new int[nums.length-1];int[] dp2 = new int[nums.length-1];if(nums.length==1){return nums[0];}if(nums.length==2){return Math.max(nums[0],nums[1]);}if(nums.length==3){return Math.max(Math.max(nums[0],nums[1]),nums[2]);}dp1[0] = nums[0];dp1[1] = Math.max(nums[0],nums[1]); dp2[0] = nums[1];dp2[1] = Math.max(nums[1],nums[2]);for(int i=2;i<nums.length-1;i++){dp1[i] = Math.max(dp1[i-1],nums[i]+dp1[i-2]);dp2[i] = Math.max(dp2[i-1],nums[i+1]+dp2[i-2]);}return Math.max(dp1[nums.length-2],dp2[nums.length-2]);}
}

337.打家劫舍 III(树形dp)

力扣题目链接(opens new window)

在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

337.打家劫舍III

看到题目的第一想法

        应该使用什么递归思路?前序?后续?

        dp数组要怎么定义?无思路

看到代码随想录之后的想法

        卡哥更多的是考虑二叉树的遍历

        每个节点两种状态,偷该节点,不偷该节点

        要获取偷该节点的最大值,和不偷该节点的最大值

        使用后序遍历,需要通过子节点偷还是不偷,来确定父节点是否要偷

        每层递归通过一个数组dp[2] 来告诉上一层,偷与不偷的值

         new int{偷该层的最大值,不偷该层的最大值}

        父节点通过左右孩子的返回值来确定偷or不偷的最大值,再往上返回

        若该节点要偷:左右孩子不偷的值相加,同时与自己的值相加

        dp[0] = left[0]+right[0]+val

        若该节点不偷:左右孩子偷与不偷的最大值                 

        dp[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1])

        递归三要素

        1 确定递归函数的参数和返回值

             参数为root,返回值为int[]

        2 确定递归函数的终止条件

                若root==null 则return new int[]{0,0}

        3 确定递归函数的执行逻辑

                后序遍历

                先递归执行root.left

                再递归执行root.right

                通过left和right返回的int数组,来确定自身的int[]并返回

        确定dp数组以及下标的含义

        确定递推函数

        dp数组初始化

        确定遍历顺序

        举例推导dp数组

自己实现过程中遇到的困难

        树形dp没见过,考虑在每个递归中新增一个dp[] 来确保内容的传递

        确定每个元素的动作比较关键,比如这个题目就是要你看该层是偷or不偷?

        然后分别讨论

        

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {//卡哥思想// 确定递归的参数和返回值// 参数 root ,返回值 dp[2] // 确定递归的终止条件// 如果为null return {0,0}// 确定递归函数的执行逻辑// 看是否偷当前节点,分为偷or不偷// 这道题是树形dp的基础题目// 使用一个数组,记录两个状态{偷当前的最高金额,不偷当前的最高金额}// 通过父节点看子节点中的金额// 每个节点有两个状态://   偷:子节点不偷,将两个子节点不偷的值(left[1],right[1])+自己节点的值// 不偷:子节点偷or不偷的最大值相加,max(left[0],left[1])+max(right[0],right[1])//确定dp数组和下标的含义// dp[0] 偷的最高金额// dp[1] 不偷的最高金额//用数组来记录小偷能偷取的最大值//确定递推公式// dp[0] = left[1]+right[1]+val;// dp[1] = Math.max(left[0],left[1])+max(right[0],right[1])//DP数组初始化//都为0//确定遍历顺序//后续遍历//举例推导dp数组int[] dp = getMax(root);return Math.max(dp[0],dp[1]);}int[] getMax(TreeNode root){if(root==null){return new int[2];}//后续遍历,左右中int[] left = getMax(root.left);int[] right = getMax(root.right);int[] dp = new int[2];//看是否偷当前的元素//偷当前的元素,则左右不偷dp[0] = left[1]+right[1] + root.val;//不偷当前的元素dp[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);return dp;}
}

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

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

相关文章

cad的模型怎么打散导入3d---模大狮模型网

将CAD中的模型打散并导入3D建模软件&#xff0c;需要以下步骤&#xff1a; 将CAD中的模型进行分组或分层&#xff1a;在CAD中&#xff0c;将模型按照不同的组或层进行分组或分层。这样可以方便地控制每个部分的显示和隐藏&#xff0c;在导入3D建模软件后&#xff0c;也可以更方…

鸿蒙开发-UI-渲染控制

鸿蒙开发-序言 鸿蒙开发-工具 鸿蒙开发-初体验 鸿蒙开发-运行机制 鸿蒙开发-运行机制-Stage模型 鸿蒙开发-UI 鸿蒙开发-UI-组件 鸿蒙开发-UI-组件-状态管理 鸿蒙开发-UI-应用-状态管理 文章目录 前言 一、渲染控制概述 二、条件渲染 1.使用规则 2.更新机制 三、循环渲染 1.接口…

POI-tl 知识整理:整理1 -> 利用模板向word中写入数据

1 文本传值 Testpublic void testText() throws Exception {XWPFTemplate template XWPFTemplate.compile("D:\\Idea-projects\\POI_word\\templates.docx");Map<String, Object> map new HashMap<>();map.put("title", "Hi, girl"…

Python 自学(八) 之模块

目录 1. import语句导入模块 P206 2. from ... import 语句导入模块 P207 3. 模块的搜索目录 sys.path P209 4. 以主程序的形式执行 __name__ P212 5. python中的包 P213 1. import语句导入模块 P206 同一目录下&…

AI教我学编程之C#类的基本概念(1)

前言 在AI教我学编程之C#类型 中&#xff0c;我们学习了C#类型的的基础知识&#xff0c;而类正是类型的一种. 目录 区分类和类型 什么是类&#xff1f; 对话AI 追问 实操 追踪属性的使用 AI登场 逐步推进 提出疑问 药不能停 终于实现 探索事件的使用 异步/交互操作 耗时操…

nginx代理七牛云http资源,节省https费用(亲测有效)

七牛云https费用太高了&#xff0c;通过配置服务器https代理到http访问&#xff01; location ~ /qiniu/(.*) { proxy_pass http://qiniu.myweb.cn/$1; proxy_set_header Host $proxy_host; proxy_set_header X-Real-IP $remote_addr; proxy_set_header X-Forwarde…

小程序学习-13

生命周期函数&#xff1a;自动按次序执行 onLoad和onReady比较常用在onReady中可以改标题&#xff08;如下图&#xff09; WXS是用来帮助开发者渲染页面结构的 过滤器&#xff1a;渲染数据之前&#xff0c;对数据做一层包装处理&#xff0c;过滤器处理的结果最终会渲染到页面上…

SpringBoot-项目部署

SpringBoot项目部署可以通过将项目打成可执行的jar包或war包来实现&#xff0c;也可以使用容器化技术如Docker将项目部署到云平台中。在部署时需要注意配置文件的位置和启动参数的设置&#xff0c;同时确保目标环境中的Java版本与项目所需的Java版本一致。部署完成后&#xff0…

Rust-类型

bool 布尔类型(bool)代表的是“是”和“否”的二值逻辑。它有两个值&#xff1a;true和false。 一般用在逻辑表达式中&#xff0c;可以执行“与”“或”“非”等运算。 char 字符类型由char表示。它可以描述任何一个符合unicode标准的字符值。在代码中&#xff0c;单个的字符…

python对自动驾驶进行模拟

使用了 Pygame 库来创建一个简单的游戏环境,模拟了一辆自动驾驶汽车在道路上行驶。汽车的位置和速度通过键盘控制&#xff0c;可以左右移动和加速减速。道路的宽度和颜色可以根据需要进行调整。 import pygame import random # 游戏窗口大小 WINDOW_WIDTH 800 WINDOW_HEIG…

【软考中级-软件设计师】day4:数据结构-线性表、单链表、栈和队列、串

大纲 线性结构 顺序存储和链式存储区别 单链表的插入和删除 真题 栈和队列 真题 串

linux强制结束某个程序的进程

远程连接上服务器&#xff0c;发现向日葵右下角的弹窗关不掉了。 查看进程 命令行输入&#xff1a; top发现两个向日葵(sunloginclient)的进程。 按q退出top 根据pid杀死进程 进入root模式 sudo sukill -9 1027 kill -9 5621成功关闭弹窗

【Java JVM】栈帧

执行引擎是 Java 虚拟机核心的组成部分之一。 在《Java虚拟机规范》中制定了 Java 虚拟机字节码执行引擎的概念模型, 这个概念模型成为各大发行商的 Java 虚拟机执行引擎的统一外观 (Facade)。 不同的虚拟机的实现中, 通常会有 解释执行 (通过解释器执行)编译执行 (通过即时编…

Python笔记08-面向对象

文章目录 类和对象构造方法内置方法封装继承类型注解多态 类只是一种程序内的“设计图纸”&#xff0c;需要基于图纸生产实体&#xff08;对象&#xff09;&#xff0c;才能正常工作 这种套路&#xff0c;称之为&#xff1a;面向对象编程 类和对象 定义类的语法如下&#xff…

SQL Server的彻底卸载的方式

这篇文章主要介绍了SQL Server的彻底卸载的方式&#xff0c;具有很好的参考价值&#xff0c;希望对大家有所帮助。如有错误或未考虑完全的地方&#xff0c;望不吝赐教 SQL Server的彻底卸载与再次安装 可能大家已经有深刻体会&#xff0c;SQL Server的卸载十分繁琐。最让人头…

前端js调用Lodop实现云打印

一、下载Lodop控件 官网&#xff1a;下载中心 - Lodop和C-Lodop官网主站 二、解压后安装 双击进行安装&#xff0c;里面有些页面文件是一些教程案例 勾选云服务工作模式 安装成功会自动启动 浏览器访问地址&#xff1a;http://localhost:8000/ 首页最下面有个教程案例跳转地址&…

Edge浏览器入门

关于作者&#xff1a; CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP&#xff0c;带领团队单日营收超千万。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、商业化变现、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览…

网络安全的威胁PPT

建议的PPT免费模板网站&#xff1a;http://www.51pptmoban.com/ppt/ 此PPT模板下载地址&#xff1a;https://file.51pptmoban.com/d/file/2023/03/20/1ae84aa8a9b666d2103f19be20249b38.zip 内容截图&#xff1a;

【AI视野·今日Robot 机器人论文速览 第七十三期】Tue, 9 Jan 2024

AI视野今日CS.Robotics 机器人学论文速览 Tue, 9 Jan 2024 Totally 40 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Robotics Papers Digital Twin for Autonomous Surface Vessels for Safe Maritime Navigation Authors Daniel Menges, Andreas Von Brandis, A…

LeetCode刷题13:回溯+剪枝解决216.组合总和 III

找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次&#xff0c;组合可以以任何顺序返回。 示例 1: 输入: k 3, n 7 输出: [[1,2,4]] 解…