当前位置：首页 > news >正文

DAY38|动态规划Part06|LeetCode:322. 零钱兑换、279.完全平方数、139.单词拆分

news 来源：原创 2025/5/15 21:41:12

LeetCode:322. 零钱兑换

基本思路

C++代码

LeetCode:279.完全平方数

C++代码

LeetCode:139.单词拆分

基本思路

C++代码

LeetCode:322. 零钱兑换

力扣题目链接

文字讲解：LeetCode:322. 零钱兑换

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？

基本思路

因为题目中明确提到，硬币的数量是无限的，显然是一个完全背包的问题。

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

dp[j]:表示将硬币填满容量为j的背包所需要的最少硬币个数为dp[j]。

确定递推公式

如果选取一维dp数组进行求解，那么dp[j]的取值可以为上一次的dp[j]的取值或者为dp[j-coins[i]]+1,又题目要求的是最小值，因此可以推导出dp[j] = min(dp[j],dp[j-coins[i]] + 1);

dp数组如何初始化

首先，根据样例提示已知，dp[0] = 0,而对于其他下标对应的值，因为要求最小值，因此我们可以自己设置一个比较大的数值，此时不妨设置为INT_MAX。

vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;

确定遍历顺序

因为是完全背包问题，并且题目所求的是最小硬币数，对于集合中元素的排列顺序如何并无要求，因此我们先遍历物品还是先遍历背包容量都可以。（以下以先遍历物品，再遍历背包为例。）

举例推导dp数组

以输入：coins = [1, 2, 5], amount = 5为例，dp[amount]为最终结果。

C++代码

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);if(amount == 0) return 0;dp[0] = 0;for(int i = 0;i<coins.size();i++){for(int j = coins[i];j<=amount;j++){if(dp[j-coins[i]] != INT_MAX){dp[j] = min(dp[j],dp[j-coins[i]] + 1);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

LeetCode:279.完全平方数

力扣题目链接

文字讲解：LeetCode:279.完全平方数

视频讲解：动态规划之完全背包，换汤不换药！

这个题目和上面的题目基本思路一样，属于换汤不换药，这里就不在进行具体分析。

C++代码

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i * i <= n; i++) { // 遍历物品for (int j = i * i; j <= n; j++) { // 遍历背包dp[j] = min(dp[j - i * i] + 1, dp[j]);}}return dp[n];}
};

LeetCode:139.单词拆分

力扣题目链接

文字讲解：LeetCode:139.单词拆分

视频讲解：动态规划之完全背包，你的背包如何装满？

基本思路

之前做过类似的题目：分割回文串，当时使用的是回溯的方法进行求解。而如果不仔细想，可能很难想到用动态规划的方法。我们其实可以把给定的字符串想象成为一个背包，而字符串列表中的字符串看作是物品，而视为物品的字符串可以重复使用，因此是一个典型的完全背包问题。

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

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

确定递推公式

如果dp[j]为true，并且[j,i]这个区间的子串出现在给定字典中，那么就说明dp[i]一定为true。

dp数组如何初始化

首先，dp[0]为true，这是为了给后续dp数组推导的基础。而对于非零下标对应的元素值则设置为false。如果设置为true，则会导致无论给定的字典是否可以组成字符串，返回值均为true。

确定遍历顺序

由于字符串的顺序是有要求的，因此显然求得是排列数。因此我们需要先遍历背包，再遍历物品。

举例推导dp[i]

以输入: s = "leetcode", wordDict = ["leet", "code"]为例，dp状态如图：

dp[s.size()]就是最终结果。

C++代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) {   // 遍历背包for (int j = 0; j < i; j++) {       // 遍历物品string word = s.substr(j, i - j); //substr(起始位置，截取的个数)if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};

DAY38|动态规划Part06|LeetCode:322. 零钱兑换、279.完全平方数、139.单词拆分

目录 LeetCode:322. 零钱兑换基本思路 C代码 LeetCode:279.完全平方数 C代码 LeetCode:139.单词拆分基本思路 C代码 LeetCode:322. 零钱兑换力扣题目链接文字讲解：LeetCode:322. 零钱兑换视频讲解：动态规划之完全背包，装满背包最…...

编程日记 2025/5/15 21:41:12

Spring事务回滚

Transactional注解 Transactional作用：就是在当前这个方法执行开始之前来开启事务，方法执行完毕之后提交事务。如果在这个方法执行的过程当中出现了异常，就会进行事务的回滚操作。 Transactional注解：我们一般会在业务层当中来控制…...

编程日记 2025/5/15 20:25:00

【目标跟踪】checkpoint文件到底是什么?

说实话，我一直决定计算机视觉是个很玄的东西，里面的很多东西都是看了概念之后云里雾里，今天就把我复现代码时遇到的不懂得讲一讲——checkpoint文件是个啥？ checkpoint文件顾名思义就是一个模型检查点文件，用于保存训练…...

编程日记 2025/5/10 8:03:54

hiprint结合vue2项目实现静默打印详细使用步骤

代码地址是：vue-plugin-hiprint: hiprint for Vue2/Vue3 ⚡打印、打印设计、可视化设计器、报表设计、元素编辑、可视化打印编辑本地安装包地址：electron-hiprint 发行版 - Gitee.com 1、先安装hipint安装包在本地 2、项目运行npm（socket.…...

编程日记 2025/5/13 2:01:58

apt和apt-get软件包管理工具-debian

apt 和 apt-get 是在基于Debian的Linux发行版（如Ubuntu）中使用的两个软件包管理工具，它们都属于APT（Advanced Package Tool）的前端工具，用于管理软件包的安装、更新、升级和删除。以下是它们的特性和一些比…...

编程日记 2025/5/15 21:30:27

小程序租赁系统开发的优势与实践探索

内容概要小程序租赁系统开发正在引起广泛关注，特别是在数字化快速发展的今天。很多企业开始意识到，小程序不仅能为他们带来更多的客户，还能极大地提高管理效率。借助小程序，用户在租赁时可以更加方便地浏览和选择产品&#xff0…...

编程日记 2025/4/11 0:52:16

sheng的学习笔记-AI-模型评估-留出法、交叉验证法、自助法

Ai目录：sheng的学习笔记-AI目录-CSDN博客评估方法： 数据集可以分为训练集，交叉验证集，测试集。训练集相当于自己做作业，验证集相当于考试测试一下自己的实力，测试集就是真刀真枪的干（当你…...

编程日记 2025/5/15 15:49:28

【Unity3D】ECS入门学习（六）状态组件 ISystemStateComponentData

当需要获知组件是否被销毁时，ECS是没有回调告知的，因此可以将组件继承于ISystemStateComponentData接口，这样即使组件的实体被销毁了，该组件本身是不会消失的，所以可以通过在组件实体销毁后，去设置状态组件…...

编程日记 2025/5/15 17:39:54

DVWA靶场第三关 CSRF

CSRF的中文叫：”跨站请求攻击“，它是通过仿照某一个特殊的网页（重置密码）来进行诱惑性攻击。难度（low级） 审计代码： <?phpif( isset( $_GET[ Change ] ) ) {// Get input$pass_new $_GE…...

编程日记 2025/5/15 20:10:56

工作流审批功能的一些概念

1. 引言在当今数字化时代，企业与组织的运营效率在很大程度上依赖于高效、精准的工作流审批系统。随着业务日益复杂且多样化，审批流程变得愈加细致和灵活。一个完善的工作流审批系统不仅能确保任务在组织内部有序流转、协调各方资源，还能实现…...

编程日记 2025/5/15 17:27:20

深度学习与图像处理（国产深度学习框架——飞桨官方指定教材）

计算机视觉从小白到大师之路《深度学习与图像处理（PaddlePaddle版）》这一本就够了 1.引言随着人工智能技术的飞速发展，各行各业对深度学习、图像处理相关领域的人才需求日益迫切。本书旨在通过系统的理论讲解与丰富的实战案例&#xff0…...

编程日记 2025/5/11 21:11:25

音视频入门知识（二）、图像篇

⭐二、图像篇视频基本要素：宽、高、帧率、编码方式、码率、分辨率其中码率的计算：码率(kbps)＝文件大小(KB)＊8／时间(秒)，即码率和视频文件大小成正比 YUV和RGB可相互转换 ★YUV（原始数据&am…...

编程日记 2025/5/15 21:05:37

计算机网络——期末复习（3）4-6章考试重点

第四章根据IPv4第1个十进制数值判断，127以下为A类，128~191为B类，192~223为C类不能分配给主机或路由器接口的：A类网络号0和127，主机号全为0或全为1私有地址（Private IP Address）是指一类专门保…...

编程日记 2025/5/12 5:08:59

openfeign自动将Boolean默认为false

最近发现项目服务间，通过openfeign调用API时，为null的Boolean类型，接收端反系列化后变为false了，经查发现是通用组件中做了处理，特记录下。主要是设置了这个 SerializerFeature.WriteNullBooleanAsFalse Bean Cond…...

编程日记 2025/5/9 23:30:08

如何实现底部导航栏

文章目录 1 概念介绍2 使用方法3 示例代码我们在上一章回中介绍了TextField Widget,本章回中将介绍BottomNavigationBar Widget。闲话休提，让我们一起Talk Flutter吧。 1 概念介绍我们在本章回中将介绍一个新的Widget:BottomNavigationBar，它就是我们经常在App中看到了底部…...

编程日记 2025/5/15 20:26:11

【深度学习基础|pip安装】pip 安装深度学习库常见错误及解决方案，附案例。

【深度学习基础|pip安装】pip 安装深度学习库常见错误及解决方案，附案例。【深度学习基础|pip安装】pip 安装深度学习库常见错误及解决方案，附案例。文章目录【深度学习基础|pip安装】pip 安装深度学习库常见错误及解决方案，附案例。1. 错…...

编程日记 2025/5/15 20:49:50

org.apache.zookeeper.server.quorum.QuorumPeerMain

QuorumPeerMain源代码 package org.apache.zookeeper.server.quorum;import java.io.IOException; import javax.management.JMException; import javax.security.sasl.SaslException; import org.apache.yetus.audience.InterfaceAudience; import org.apache.zookeeper.audi…...

编程日记 2025/5/13 18:29:06

如何在yolov8中使用ATSS策略

在yolov8中使用的标签匹配策略是TAL,本篇文章解析一下ATSS代码相关实现以及如何把ATSS放到yolov8中使用看过本专栏中的另外两篇文章的同学应该对v8解析box那一套很熟悉了，ATSS的第一步就是去得到一系列的anchor-box(如果是anchor-based检测方法)或者anchor-point(基…...

编程日记 2025/5/15 17:26:30

常见的邮件协议SMTP和POP3

常见的邮件协议包括SMTP和POP3，SMTP用来发送邮件，POP3用来接收邮件信息。 SMTP SMTP 是一种用于发送电子邮件的协议。它的主要作用是将**电子邮件**从邮件客户端（如 Outlook、Thunderbird）或邮件服务器发送到接收服务器。 SMTP …...

编程日记 2025/5/15 20:34:09

线性代数行列式

目录二阶与三阶行列式二元线性方程组与二阶行列式三阶行列式全排列和对换排列及其逆序数对换 n阶行列式的定义行列式的性质二阶与三阶行列式二元线性方程组与二阶行列式若是采用消元法解x1、x2的话则得到以下式子有二阶行列式的规律可得：分…...

编程日记 2025/5/15 20:45:35

cin/cout性能问题讨论和优化⽅法

样例解析： 在上面的两个案例中，我们发现虽然代码的逻辑是相同的，唯一的不同点在于scanf和cout的使用区别，一份超时一份ac，这是为什么呢？是否有可行的优化方法呢？ 背景知识： 在 C 中…...

编程日记 2025/5/1 10:03:32

轮胎识别数据集，可对生产流水线里的轮胎图片标注，支持yolo，coco json，voc xml格式的标注，一共785张采集图片

轮胎识别数据集，可对生产流水线里的轮胎图片标注，支持yolo，coco json，voc xml格式的标注，一共785张采集图片数据集分割训练组90％ 706图片有效集6% 46图片测试集4% 33图片预处理…...

编程日记 2025/5/15 20:57:47

ARM64 Windows 10 IoT工控主板运行x86程序效率测试

ARM上的 Windows 10 IoT 企业版支持仿真 x86 应用程序，而 ARM上的 Windows 11 IoT 企业版则支持仿真 x86 和 x64 应用程序。英创推出的名片尺寸ARM64工控主板ESM8400，可预装正版Windows 10 IoT企业版操作系统，x86程序可无需修改而直接在ESM84…...

编程日记 2025/5/14 22:58:09

Git核心概念

版本控制什么是版本控制版本控制是一种记录一个或若干文件内容变化，以便将来查阅特定版本修订情况的系统。除了项目源代码，你可以对任何类型的文件进行版本控制。为什么要版本控制有了它你就可以将某个文件回溯到之前的状态，甚至将整…...

编程日记 2025/5/3 12:34:32

Spring Boot spring.factories文件详细说明

优质博文：IT-BLOG-CN 前言：经常看到 spring.factories 文件，却没有对它进行深入的了解和分析，今天我们就一起揭开面纱看看它的内在。 spring.factories 文件是 Spring Boot 自动配置机制的核心部分之一。它位于每个 Spring Boo…...

编程日记 2025/5/15 4:23:07

QWidget应用封装为qt插件,供其他qt应用调用

在之前的文章中,有介绍通过QProcess的方式启动QWidget应用,然后将其窗口嵌入到其他的qt应用中,作为子窗口使用.这篇文章主要介绍qt插件的方式将QWidget应用的窗口封装为插件,然后作为其他Qt应用中的子窗口使用. 插件优点: 与主程序为同一个进程,免去了进程间繁琐的通信方式,…...

编程日记 2025/5/12 13:56:15

Nginx的性能分析与调优简介

Nginx的性能分析与调优简介一、Nginx的用途二、Nginx负载均衡策略介绍与调优三、其他调优方式简介四、Nginx的性能监控一、Nginx的用途 ‌Nginx是一种高性能的HTTP和反向代理服务器，最初作为HTTP服务器开发，主要用于服务静态内容如HTML文件、图像、视…...

编程日记 2025/5/8 9:56:26

学习threejs，导入CTM格式的模型

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：threejs gis工程师文章目录一、🍀前言1.1 ☘️THREE.ColladaLoader DAE模…...

编程日记 2025/5/11 22:23:52

Lua元表

哈喽，好久没有做记录了，最近刚好有时间打算整理一些基础常用内容，先做一期关于Lua相关的内容热热身。如果内容有误，欢迎大家指出我会积极做出响应。在Lua中，元表（metatable） 和元方法&#xf…...

编程日记 2025/5/9 17:50:54

pyqt和pycharm环境搭建

安装 python安装： https://www.python.org/downloads/release/python-3913/ python3.9.13 64位(记得勾选Path环境变量) pycharm安装： https://www.jetbrains.com/pycharm/download/?sectionwindows community免费版换源： pip config se…...

编程日记 2025/5/13 15:14:01

overleaf中的includegraphics设置图片缩放，居中显示

overleaf中的includegraphics设置图片缩放，居中显示 \includegraphics[width=0.5\textwidth]{example.jpg} \centering 在使用 \includegraphics 命令插入图片时，可以通过设置其参数来缩小图片的显示尺寸，以下是几种常见的方法：设置宽度或高度按比例缩小宽度：可以使用…...

编程日记 2025/5/6 8:56:01

USB免驱IC读写器QT小程序开发

USB免驱全协议IC卡读写器QT小程序开发，读取15693卡。 QT小程序UI开发界面： QT程序代码mainWindow.cpp代码如下： MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this); }MainWind…...

编程日记 2025/5/9 19:51:04

Wend看源码-Java-集合学习(List)

摘要本篇文章深入探讨了基于JDK 21版本的Java.util包中提供的多样化集合类型。在Java中集合共分类为三种数据结构：List、Set和Queue。本文将详细阐述这些数据类型的各自实现，并按照线程安全性进行分类，分别介绍非线程安全与线程安全的实现方…...

编程日记 2025/5/15 9:41:05

只谈C++11新特性 - 删除函数

删除函数背景在 C11 之前，C 的类默认会生成拷贝构造函数和赋值运算符。这在某些情况下会引发问题，尤其是在我们希望明确禁止某些操作时。假设我们有一个类，它不希望被拷贝，但未明确声明拷贝构造函数和赋值运算符，这…...

编程日记 2025/5/12 17:14:21

uniapp 文本转语音

uniapp 文本转语音基于 Minimax API 的 UniApp 文本转语音工具，支持文本分段、队列播放、暂停恢复等功能。目前只内置了 Minimax文本转语音Minimax 的语音生成技术以其自然、情感丰富和实时性强而著称 API_KEY、GroupId 获取方法 https://platform.minimaxi.com…...

编程日记 2025/5/14 8:27:58

1.RPC基本原理

文章目录 RPC1.定义2.概念3.优缺点4.RPC结构5.RPC消息协议5.1 消息边界5.2 内容5.3 压缩 6.RPC的实现6.1 divide_protocol.py6.2 server.py6.3 client.py RPC 1.定义远程过程调用(remote procedure call) 2.概念广义:所有通过网络进行通讯,的调用统称为RPC调用狭义:不采…...

编程日记 2025/5/14 17:35:38

如何从 0 到 1 ，打造全新一代分布式数据架构

导读：本文从 DIKW（数据、信息、知识、智慧） 模型视角出发，探讨数字世界中数据的重要性问题。接着站在业务视角，讨论了在不断满足业务诉求（特别是 AI 需求）的过程中，数据系统是如何一…...

编程日记 2025/5/15 1:50:10

PyPika：Python SQL 查询构建器

什么是 PyPika？ Pypika 是一个 Python 库，用于构建 SQL 查询。它提供了一种简洁、直观的方式来生成 SQL 语句，而无需手动编写复杂的 SQL 代码。Pypika 的设计哲学是尽可能地接近 SQL 的自然语法，同时利用 Python 的强大功能来简化…...

编程日记 2025/5/12 17:18:21

剑指Offer|LCR 014. 字符串的排列

LCR 014. 字符串的排列给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。换句话说，第一个字符串的排列之一是第二个字符串的子串。示例 1： 输入: s1 "ab" s2 "eidbaooo" 输出: True 解…...

编程日记 2025/5/13 21:45:36

通过百度api处理交通数据

通过百度api处理交通数据 1、读取excel获取道路数据 //道路名称Data EqualsAndHashCode public class RoadName {ExcelProperty("Name")private String name; }/*** 获取excel中的道路名称*/private static List<String> getRoadName() {// 定义文件路径&…...

编程日记 2025/5/14 17:59:55

使用亚马逊针对 PyTorch 和 MinIO 的 S3 连接器实现可迭代式数据集

2023 年 11 月，Amazon 宣布推出适用于 PyTorch 的 S3 连接器。适用于 PyTorch 的 Amazon S3 连接器提供了专为 S3 对象存储构建的 PyTorch 数据集基元（数据集和数据加载器）的实现。它支持用于随机数据访问模式的地图样式数据集和用于流式处理…...

编程日记 2025/5/11 9:38:21

c++编译过程初识

编译过程预处理：主要是执行一些预处理指令，主要是#开头的代码，如#include 的头文件、#define 定义的宏常量、#ifdef #ifndef #endif等条件编译的代码，具体包括查找头文件、进行宏替换、根据条件编译等操作。 g -E example.cpp -…...

编程日记 2025/5/11 5:24:00

Java旅程（五）Spring 框架与微服务架构了解 JVM 内部原理和调优

在现代企业级应用中，Spring 框架和微服务架构已经成为主流技术，而 Java 虚拟机（JVM）的理解和调优对于保证应用的高性能和稳定性也至关重要。本篇博客将深入讲解 Spring 框架与微服务架构，并进一步探讨 JVM 内部原理和调…...

编程日记 2025/5/11 21:34:44

SWAT-MODFLOW地表水-地下水耦合模型建模；QSWATMOD实现SWAT-MODFLOW联合

SWAT-MODFLOW地表水-地下水耦合建模的应用重要性： 1.全面性：耦合模型能够同时考虑地表水和地下水的相互作用，提供了一个更全面的水文循环模拟框架。2.准确性：通过耦合地表水和地下水模型，可以提高水文模拟的准确性&…...

编程日记 2025/5/11 0:39:07

Azure Function 解决跨域问题

这边前端call本地部署的azure function出现了跨域问题，搜索一下解决方案直接修改local.setting.json，在其中添加CORS配置为通配符”*”，就行了 local.settings.json {"IsEncrypted": false,"Values": {"PYTHON_E…...

编程日记 2025/4/21 1:30:59

金融租赁系统的创新发展与市场竞争力提升探讨

内容概要随着经济的快速发展，金融租赁系统逐渐成为金融市场中不可或缺的一环。它不仅提供了灵活的资金解决方案，还促进了企业的资本结构优化与资源配置效率。因此，了解该系统的市场背景与发展现状至关重要。在现今环境下，新兴…...

编程日记 2025/5/14 23:06:36

Rust: offset祼指针操作

offset是偏移元素个数，不是字节数！ fn main(){let student_a Student{id:20240001,name:"张三娃".into(),class_id:3,age:14,grade:1};let student_b Student{id:20240002,name:"李四牛".into(),class_id:3,age:15,grade:1};let …...

编程日记 2025/5/14 20:25:10

【C#】WPF设置Separator为垂直方向

1. 方法1 <Separator BorderBrush"Gray"><Separator.LayoutTransform><RotateTransform Angle"90" /></Separator.LayoutTransform> </Separator>2. 方法2 <Separator Style"{StaticResource {x:Static ToolBar.S…...

编程日记 2025/5/10 4:28:16