代码随想录算法训练营第四十六天 _ 动态规划_198.打家劫舍、213.打家劫舍II、337.打家劫舍 III。
学习目标:
动态规划五部曲:
① 确定dp[i]的含义
② 求递推公式
③ dp数组如何初始化
④ 确定遍历顺序
⑤ 打印递归数组 ---- 调试
引用自代码随想录!
60天训练营打卡计划!
学习内容:
198.打家劫舍
- 动态规划五步曲:
① 确定dp[i]的含义 : 包含 下标i 偷得最大的金币数。
② 求递推公式 : dp[i] = max(dp[i-2] + nums[i] , dp[i-1])
偷 i:dp[i-2] + nums[i]
不偷 i:dp[i-1]
③ dp数组如何初始化 : dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
④ 确定遍历顺序 : 从前向后
// 动态规划
class Solution {public int rob(int[] nums) {int size = nums.length;int[] dp = new int[size];// 初始化dp[0] = nums[0];if(size > 1)dp[1] = Math.max(nums[0], nums[1]);// 递归逻辑for(int i = 2; i < size; i++){dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);}return dp[size-1];}
}
213.打家劫舍II
- 给定的数组连城环啦。
- 动态规划五步曲:
① 确定dp[i]的含义 :包含 下标i 偷得最大的金币数。
② 求递推公式 : dp[i] = max(dp[i-2] + nums[i] , dp[i-1])
偷 i:dp[i-2] + nums[i]
不偷 i:dp[i-1]
③ dp数组如何初始化 : dp[start] = nums[start]
dp[start+1] = Math.max(nums[start],nums[start+1])
④ 确定遍历顺序 : 从前向后
class Solution {public int robAsist(int[] nums, int start, int end) {// 包含 物品i 在内的最大的金币数。int[] dp = new int[end];// 初始化dp[start] = nums[start];dp[start+1] = Math.max(nums[start],nums[start+1]);// 递归逻辑for(int j = start+2; j < end; j++){dp[j] = Math.max(dp[j-1], dp[j-2]+nums[j]);}return dp[end-1];}public int rob(int[] nums) {if(nums.length == 1) return nums[0];if(nums.length == 2) return nums[0] > nums[1] ? nums[0] : nums[1];int len = nums.length;// 因为是环,有两种情况// 一、不选择头节点,这样就可以选尾节点// 二。不选择尾节点,这样就可以选头节点// 且规则是左闭右开return Math.max(robAsist(nums, 0, len - 1), robAsist(nums, 1, len));}
}
337.打家劫舍 III
- 树形的数据结构。(后序遍历 – 左右中)
- 递归三部曲:
递归函数的传入参数和返回值;
递归函数的结束条件;
递归函数的最小逻辑。 - 动态规划五步曲:
① 确定dp[i]的含义 : dp[0] : 不偷当前节点的最大金币数 dp[1]:偷当前节点的最大金币数
② 求递推公式 : 递归传给上一层
偷根节点: dp[1] = node.val + leftdp[0] + rightdp[0]
不偷根节点: dp[0] = max(leftdp[0],leftdp[1]) + max(rightdp[0],rightdp[1])
③ dp数组如何初始化 : dp[0] = 0 dp[1] = 0
④ 确定遍历顺序 : 从叶子节点到根节点
/*** 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[] robTree(TreeNode node) {// 递归函数的结束条件if(node == null) return new int[]{0,0};// 递归函数的最小逻辑int[] leftdp = robTree(node.left);int[] rightdp = robTree(node.right);// 不偷根节点int val1 = Math.max(leftdp[0], leftdp[1]) + Math.max(rightdp[0], rightdp[1]);// 偷根节点int val2 = node.val + leftdp[0] + rightdp[0];return new int[]{val1, val2};}public int rob(TreeNode root) {int[] dp = robTree(root);return dp[0] > dp[1] ? dp[0] : dp[1];}
}
学习时间:
- 上午两个半小时,整理文档半小时。
相关文章:
代码随想录算法训练营第四十六天 _ 动态规划_198.打家劫舍、213.打家劫舍II、337.打家劫舍 III。
学习目标: 动态规划五部曲: ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录! 60天训练营打卡计划! 学习内容: 198.打家劫舍 动态规划五步曲&a…...
ffmpeg编译问题
利用ffmpeg实现一个播放器,ffmpeg提供动态库,但是编译链接的时候遇到下面的问题: ../ffmpegWidgetPlayer/videoplayerwidget.cpp:23: error: undefined reference to sws_freeContext(SwsContext*) ../ffmpegWidgetPlayer/videoplayerwidget.…...
【flink番外篇】1、flink的23种常用算子介绍及详细示例(3)-window、distinct、join等
Flink 系列文章 一、Flink 专栏 Flink 专栏系统介绍某一知识点,并辅以具体的示例进行说明。 1、Flink 部署系列 本部分介绍Flink的部署、配置相关基础内容。 2、Flink基础系列 本部分介绍Flink 的基础部分,比如术语、架构、编程模型、编程指南、基本的…...
centos7做gitlab数据灾备项目地址指向问题
如果你在 CentOS 7 上使用 GitLab 时,它回复的数据指向了另一个服务器的地址,可能是因为配置文件中的一些设置不正确。 要解决这个问题,可以尝试以下几个步骤: 检查 GitLab 配置文件:打开 GitLab 的配置文件…...
leetcode:93. 复原 IP 地址
复原 IP 地址 中等 1.4K 相关企业 有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。 例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但…...
玄子Share-CSS3 弹性布局知识手册
玄子Share-CSS3 弹性布局知识手册 Flexbox Layout(弹性盒布局)是一种在 CSS 中用于设计复杂布局结构的模型。它提供了更加高效、简便的方式来对容器内的子元素进行排列、对齐和分布 主轴和交叉轴 使用弹性布局,最重要的一个概念就是主轴与…...
Nat easy IP ACL
0表示匹配,1表示任意(主机位0.0.0.255(255主机位)) rule deny source 192.168.2.1 0 设置拒绝192.168.2.1的主机通过 记住将其应用到接口上 [AR2]acl 2000 //创建基本ACL [AR2-acl-basic-2000]rule deny source 192…...
Numpy数组的数据类型汇总 (第4讲)
Numpy数组的数据类型 (第4讲) 🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ�…...
通讯app:
为了开发一个即时通讯的app,包含发送文字、语音、视频以及视频通话的功能,我们需要考虑以下的技术栈和实现步骤: 技术栈建议: 前端:React Native 或 Flutter 用于跨平台移动应用开发。后端:ThinkPHP Wor…...
【Backbone】TransNeXt:最新ViT模型(原理+常用神经网络汇总)
文章目录 一、近几年神经网络 Backbone 回顾1.Densenet 与 Resnet2.CBP3.SENet4.GCNet5.DANet6.PANet 与 FPN7.ASPP8.SPP-net9.PSP-net10.ECA-Net 二、TransNeXt(2023)1.提出问题2.Aggregated Pixel-focused Attention2.1 Pixel-focused Attention&#…...
使用Java将图片添加到Excel的几种方式
1、超链接 使用POI,依赖如下 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId><version>4.1.2</version></dependency>Java代码如下,运行该程序它会在桌面创建ImageLinks.xlsx文件。 …...
用什么台灯对眼睛最好?考公护眼台灯推荐
之前我一直觉得,孩子近视,是因为玩手机太多,看电子产品的时间过长,但后来控制孩子看电子产品时间的触底反弹与越来越深的度数告诉我,孩子近视的真正原因,我根本没有找到,后来看到一篇报告&#…...
【嵌入式开发 Linux 常用命令系列 4.2 -- .repo 各个目录介绍】
文章目录 概述.repo 目录结构manifests/default.xmlManifest 文件的作用default.xml 文件内容示例linkfile 介绍 .repo/projects 子目录配置和管理configHEADhooksinfo/excludeobjectsrr-cache 工作区中的对应目录 概述 repo 是一个由 Google 开发的版本控制工具,它…...
【C++学习手札】基于红黑树封装模拟实现map和set
🎬慕斯主页:修仙—别有洞天 💜本文前置知识: 红黑树 ♈️今日夜电波:漂流—菅原纱由理 2:55━━━━━━️💟──────── 4:29 …...
linux查看当前路径的所有文件大小;linux查看当前文件夹属于什么文件系统
1:指令查看当前路径所有文件内存空间大小;这样可以方便查询每个文件大小情况,根据需要进行删除 df -h // 根目录 du -ah --max-depth1 // 一级目录 虚拟机 du -ah -d 1 // 一级目录 设备使用 du -ah --max-depth2 // 二…...
PPT插件-好用的插件-超级文本-大珩助手
常用字体 内置了大量的常用字体,方便快捷的一键更换字体,避免系统字体过多卡顿 文字整理 包含删空白行、清理编号、清理格式,便于处理从网络上复制的资料 文本打散与合并 包含文本打散、文本合并,文本打散可实现将一个文本打散…...
Kafka中的Topic
在Kafka中,Topic是消息的逻辑容器,用于组织和分类消息。本文将深入探讨Kafka Topic的各个方面,包括创建、配置、生产者和消费者,以及一些实际应用中的示例代码。 1. 介绍 在Kafka中,Topic是消息的逻辑通道࿰…...
LAMP部署
目录 一、安装apache 二、配置mysql 三、安装php 四、搭建论坛 4、安装另一个网站 一、安装apache 1.关闭防火墙,将安装Apache所需软件包传到/opt目录下 systemctl stop firewalld systemctl disable firewalld setenforce 0 httpd-2.4.29.tar.gz apr-1.6.2.t…...
DouyinAPI接口开发系列丨商品详情数据丨视频详情数据
电商API就是各大电商平台提供给开发者访问平台数据的接口。目前,主流电商平台如淘宝、天猫、京东、苏宁等都有自己的API。 二、电商API的应用价值 1.直接对接原始数据源,数据提取更加准确和完整。 2.查询速度更快,可以快速响应用户请求实现…...
AWS Remote Control ( Wi-Fi ) on i.MX RT1060 EVK - 3 “编译 NXP i.MX RT1060”( 完 )
此章节叙述如何修改、建构 i.MX RT1060 的 Sample Code“aws_remote_control_wifi_nxp” 1. 点击“Import SDK example(s)” 2. 选择“MIMXRT1062xxxxA”>“evkmimxrt1060”,并确认 SDK 版本后,点击“Next>” 3. 选择“aws_examples”>“aw…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG
TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码:HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
