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

【LeetCode 热题 100】动态规划系列

news 来源：原创 2025/6/20 15:45:21

📁 70. 爬楼梯

状态标识：爬到第i层楼梯时，有多少种方法。

状态转移方程：dp[i] = dp[i-1] + dp[i-2]，表示从走一步和走两步的方式。

初始化：dp[1] = 1 , dp[2] = 2。

返回值：dp[n]，即走到第n层可以有多少种爬法。

class Solution {
public:int climbStairs(int n) {int dp[50] = { 0  , 1 , 2};for(int i = 3 ; i <= n ; ++i){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

📁 118. 杨辉三角

就是一道找规律的题目，每一列第一个和每一行最后一个初始化为1，其余的为左上方和右上方数之和。

状态转移方程：dp[i][j] = dp[i-1][j] + dp[i-1][j-1]。

vector<vector<int>> generate(int numRows) {vector<vector<int>> dp(numRows);for(int i = 0 ; i < numRows ; ++i)dp[i].resize(i + 1) , dp[i][i] = 1 , dp[i][0] = 1;for(int i = 2 ; i < numRows ; ++i)for(int j = 1 ; j < i ; ++j)dp[i][j] = dp[i-1][j] + dp[i-1][j-1];return dp;}

📁 198. 打家劫舍

状态表示：dp[i]表示偷窃到第 i 加时，此时偷取到的最大金额。

转移方程：dp[i] = max(dp[i-1] , dp[i-2] + num[i-1])

初始化：dp[0] = nums[1]，第一家是可以直接偷取到的。

返回值：返回dp[n]，即偷取到最后一家是此时的最大金额。

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

📁 279. 完全平方数

状态标识：dp[i]表示和为 i 的完全平方数的最小数量。

转移方程：dp[i] = min(dp[i] , dp[i - j * j] + 1)。j * j 表示小于i的完全平方数

初始化：dp[i] = i，将当前数字更新为最大结果，即最坏结果，表示 i 可以由 i 个 1 组成。

返回值：返回dp[n]。

动态规划本身就是一个递推的过程，我们从前往后枚举，当枚举到第i个数的时候，意味着i-1都被枚举完了。因此，当一个数减去一个完全平方数时剩余和一定能在dp数组中找到，并且剩余和已经知道最小完全平方数的最小数量，因此，我们结果只需要在此基础上+1即可。

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1 , 0);for(int i = 1 ; i <= n ; ++i){dp[i] = i;for(int j = 2 ; j * j <= i ; ++j){dp[i] = min(dp[i] , dp[i-j*j] + 1);}}return dp[n];}
};

📁 322. 零钱兑换

这道题可以看做是上一题的一种变形。

状态标识：dp[i]表示金额为 i 的时，需要的最少硬币数量。

转移方程：dp[i] = min(dp[i] , dp[i - coin] + 1)。

初始化：dp[0] = 0，其余将当前数字更新0x3f3f3f3f，表示目前不能通过硬币各个金额组成选择不能组成（方便返回值的处理）

返回值：返回dp[amoun]。需要注意的是，如果dp[amoun] = 0x3f3f3f3f，需要返回-1。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, 0x3f3f3f3f);dp[0] = 0;for(int i = 1 ; i <= amount ; ++i){for(auto coin : coins)if(coin <= i)dp[i] = min(dp[i] , dp[i-coin] + 1);}return dp[amount]==0x3f3f3f3f ? -1 : dp[amount];}
};

📁 139. 单词拆分

状态表示：以某个字符为结尾的字符串，能否由wordDict中的word拼接形成。为了快速查找字典里面的单词，我们是用哈希系列容器存储单词。

转移方程：dp[i] = str(j , i)是字典里面的单词 && dp[j - 1]。

初始化：dp[0] = true，表示只有一个字符，并且成功在哈希表中找到。

返回值：dp[n]，以n为结尾的字符串，能否由wordDict中的word拼接形成。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();vector<int> dp(n + 1 , false);dp[0] = true;unordered_set<string> hash;for(auto word : wordDict)hash.insert(word);for(int i = 1 ; i <= n ; ++i){for(int j = i; j > 0 ; --j){string tmp = s.substr(j - 1, i - j + 1);if(hash.find(tmp) != hash.end())dp[i] = dp[j - 1];if(dp[i] == true)break;}}return dp[n];}
};

📁 300. 最长递增子序列

如果想要有一个子序列尽可能的多，那么就要使得子序列中元素相较于前一个元素上升趋势尽可能小，与后一个元素上升趋势尽可能大。通过一个数组dp来维护递增子序列。

1. 当新来一个元素时，如果大于尾部元素，直接插入；

2. 如果小于尾部元素，那么之前就一定存在比他的的一个或者多个元素，因此我们将这个新的较小值更新到子序列中第一个比它的的元素中，使得子序列上升趋势变得更小。

使用二分查找算法，查找子序列中第一个比新来较小值大的的元素，然后更新。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i = 1 ; i < n ; ++i){if(nums[i] > ret.back())ret.push_back(nums[i]);else{int left = 0 , right = ret.size() - 1;while(left < right){int mid = (left + right) >> 1;if(ret[mid] < nums[i])left = mid + 1;    elseright = mid;}ret[left] = nums[i];}}return ret.size();}
};

📁 152. 乘积最大子数组

遍历数组，每次遍历时，记录乘积最大值，更新结果。问题是乘积最大值怎么更新？

当一个新元素x到来时，与之前连续子数组乘积最大值maxS进行比较 max( x , maxS)。

1. 如果 x 是正数，且maxS也是正数，那么会得到一个更大的正数。

2. 如果 x 是正数，maxS是负数，那么会得到一个更小的数值。

3. 如果 x 是负数，maxS是正数，那么会得到一个更小的数值。

4. 如果 x 是负数，maxS是负数，那么会得到一个更大的数值。

但如果我们记录一个较小值minS，那么 x 如果负数，minS也是负数，就会得到一个更大的值。

即，如果x是正数，必须有一个最大值相乘才能得到更大值；如果x是负数，必须和一个最小值相乘才能得到一个更大值。

核心：负数 x 大=小；负数 x 小=大；正数 x 大=大；正数 x 小=小

class Solution {
public:int maxProduct(vector<int>& nums) {int ans = nums[0] , maxI = nums[0] , minI = nums[0];int n = nums.size();for(int i = 1 ; i < n ; ++i){int tmp = maxI;/*nums[i] * tmp: 如果nums[i]是正数, 得到更大值nums[i] * minI: 如果nums[i]是负数, 得到更大值*/maxI = max(max(nums[i] , nums[i] * tmp) , nums[i] * minI);/*nums[i] * minI: 如果nums[i]是正数, 得到更小值nums[i] * tmp: 如果nums[i]是负数, 得到更小值*/minI = min(min(nums[i] , nums[i] * minI) , nums[i] * tmp);ans = max(ans , maxI);}return ans;}
};

📁 416. 分割等和子集

就是一道简单的01背包问题。首先判断个数组总和是否为偶数，如果是奇数直接返回false，因为不可能将数组分割成元素和相等的两个子集；如果sum是偶数，令target = sum / 2。需要判断从数组中能否选出一些数，使得这些数之和=target。

状态标识：dp[i][j]: 前i个元素中能否恰好选出总和为 j 的子集

转移方程：dp[i][j] = (不选第i件，dp[i-1][j]) or (选第i件 dp[i-1][j-nums[i]])

返回值：dp[n][target]。

此外，采用滚动数组进行优化，使得只能一维数组就可以完成上述操作，只不是从前往后遍历改成往后往前遍历。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(auto e : nums)sum += e;if(sum % 2 != 0)return false;int n = nums.size();int target = sum / 2;vector<bool> dp(target + 1 , false);dp[0] = true;for(int i = 1 ; i <= n ; ++i){for(int j = target ; j >= nums[i-1] ; --j)dp[j] = dp[j] || dp[j- nums[i-1]];}return dp[target];}
};

📁 32. 最长有效括号

状态表示: dp[i]表示以s[i]为结尾并且包含s[i]的最长有效括号。

状态转移方程:

1. s[i] =='(' 无法组成有效括号 dp[i] = 0;

2. s[i] ==')' 取决于之前的有效括号

情况1: s[i-1] == '('

dp[i] = dp[i-2] + 2;

情况2: s[i-1] == ')'

这里如果想要包含s[i]组成有效括号的字符串，

必须满足 ((...)) 这种形式 , 其中...是未知个数的有效括号子串。

即 s[i - dp[i-1] - 1] == '('

所以, dp[i] = dp[i-1] + dp[i - dp[i-1] - 2 ] + 2;

初始化:

dp[0] = 0 一个字符不能构成有效括号

class Solution {
public:int longestValidParentheses(string s) {int n = s.size();int ans = 0;vector<int> dp(n + 1 , 0);for(int i = 1 ; i <= n ; ++i){if(s[i] == ')'){if(s[i-1] == '(')dp[i] = (i - 2 >= 0 ? dp[i-2] : 0) + 2;else if(i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(')dp[i] = dp[i - 1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);}ans = max(ans , dp[i]);}return ans;}
};

【LeetCode 热题 100】动态规划系列

📁 70. 爬楼梯状态标识：爬到第i层楼梯时，有多少种方法。状态转移方程：dp[i] dp[i-1] dp[i-2]，表示从走一步和走两步的方式。初始化：dp[1] 1 , dp[2] 2。返回值：dp[n]，即走到…...

编程日记 2025/6/20 15:45:21

刷leetcodehot100返航版--双指针5/16

for (int i 0, j 0; i < n; i ) { while (j < i && check(i, j)) j ; // 具体问题的逻辑 } 常见问题分类： (1) 对于一个序列，用两个指针维护一段区间 (2) 对于两个序列，维护某种次序，比如归并排序中…...

编程日记 2025/6/20 15:20:08

DAY24元组和OS模块

元组元组的特点： 有序，可以重复，这一点和列表一样元组中的元素不能修改，这一点非常重要，深度学习场景中很多参数、形状定义好了确保后续不能被修改。很多流行的 ML/DL 库（如 TensorFlow, PyTorch, Num…...

编程日记 2025/5/27 6:33:39

CSS：三大特性

文章目录一、层叠性二、继承性三、优先级一、层叠性二、继承性可以在MDN网站上查看属性是否可以被继承例如color 三、优先级...

编程日记 2025/5/22 8:16:04

Cross-Site Scripting（XSS）

1. XSS介绍跨站脚本攻击（Cross-Site Scripting）简称XSS，人们经常将跨站脚本攻击（Cross Site Scripting）缩写为CSS，但这会与层叠样式表（Cascading Style Sheets，CSS）的缩…...

编程日记 2025/5/27 5:26:51

掌握HTML文件上传：从基础到高级技巧

HTML中input标签的上传文件功能详解一、基础概念 1. 文件上传的基本原理在Web开发中，文件上传是指将本地计算机中的文件（如图片、文档、视频等）传输到服务器的过程。HTML中的<input type"file">标签是实现这一功能的基础…...

编程日记 2025/5/29 9:20:57

WebRTC中的几个Channel

一、我指的是谁？ 以视频为例，常见的有：MediaChannel、VideoMediaChannel、WebRtcVideoChannel、BaseChannel、VideoChannel，那么，为什么要这么多Channel，只写一个叫做SuperChannel行不行（很多程…...

编程日记 2025/5/29 17:02:00

【设计模式】- 行为型模式1

模板方法模式定义了一个操作中的算法骨架，将算法的一些步骤推迟到子类，使得子类可以不改变该算法结构的情况下重定义该算法的某些步骤【主要角色】： 抽象类：给出一个算法的轮廓和骨架（包括一个模板方法和若干基…...

编程日记 2025/5/18 8:45:57

容器化-k8s-使用和部署

一、K8s 使用 1、基本概念集群：由 master 节点和多个 slaver 节点组成，是 K8s 的运行基础。节点：可以是物理机或虚拟机，是 K8s 集群的工作单元，运行容器化应用。Pod： K8s 中最小的部署单元，一个 Pod 可以包含一个或多个紧密相关的容器，这些容器共享网络和存储资源。…...

编程日记 2025/5/28 7:56:32

黑马k8s（九）

1.Pod-生命周期概述 2.Pod生命周期-创建和终止 3.Pod生命周期-初始化容器...

编程日记 2025/5/28 14:47:32

Android trace中CPU的RenderThread与GPU

Android trace中CPU的RenderThread与GPU RenderThread是系统的GPU绘制线程，GPU渲染就是通常所谓的硬件加速，如果应用关闭硬件加速，就没有了RenderThread，只有UI Thread，即Android主线程。 Android GPU渲染SurfaceFlin…...

编程日记 2025/5/18 10:17:14

测试工程师如何学会Kubernetes(k8s)容器知识

Kubernetes(K8s)作为云原生时代的关键技术之一，对于运维工程师、开发工程师以及测试工程师来说，都是一门需要掌握的重要技术。作为一名软件测试工程师，学习Kubernetes是一个有助于提升自动化测试、容器化测试以及云原生应用测试能力的重要过程…...

编程日记 2025/5/29 9:51:45

接触感知钳位电路分析

以下是NG板接触感知电路的原理图。两极分别为P3和P4S，电压值P4S < P3。电路结构分两部分，第一部分对输入电压进行分压钳位。后级电路使用LM113比较器芯片进行电压比较，输出ST接触感知信号。钳位电路输出特性分析输出电压变化趋势&a…...

编程日记 2025/5/18 9:08:21

码蹄集——圆包含

MT1181 圆包含输入2个圆的圆心的坐标值（x，y）和半径，判断断一个圆是否完全包含另一个圆，输出YES或者NO。另：内切不算做完全包含。格式输入格式：输入整型，空格分隔。每行输入一组…...

编程日记 2025/6/1 12:40:17

ConcurrentSkipListMap的深入学习

目录 1、介绍 1.1、线程安全 1.2、有序性 1.3、跳表数据结构 1.4、API 提供的功能 1.5、高效性 1.6、应用场景 2、数据结构 2.1、跳表（Skip List） 2.2、节点类型： 1.Node 2.Index 3.HeadIndex 2.3、特点 3、选择层级 3.1、随…...

编程日记 2025/5/30 0:08:41

ProfibusDP主站转modbusTCP网关接DP从站网关通讯案例

ProfibusDP主站转modbusTCP网关接DP从站网关通讯案例在工业自动化领域，Profibus DP和Modbus TCP是两种常见的通信协议。Profibus DP广泛应用于过程自动化、工厂自动化等场景，而Modbus TCP则常见于楼宇自动化、能源管理等领域。由于设备和系统之间往往存…...

编程日记 2025/5/22 8:21:53

第一次做逆向

题目来源：ctf.show 1、下载附件，发现一个exe和一个txt文件看看病毒加没加壳，发现没加那就直接放IDA 放到IDA找到main主函数，按F5反编译工具就把他还原成类似C语言的代码然后我们看逻辑，将flag.txt文件的内容进行加…...

编程日记 2025/5/29 12:37:43

【项目】自主实现HTTP服务器：从Socket到CGI全流程解析

00 引言在构建高效、可扩展的网络应用时，理解HTTP服务器的底层原理是一项必不可少的技能。现代浏览器与移动应用大量依赖HTTP协议完成前后端通信，而这一过程的背后，是由网络套接字驱动的请求解析、响应构建、数据传输等一系列机制所支撑…...

编程日记 2025/5/24 23:03:38

AI最新资讯，GPT4.1加入网页端、Claude 3.7 Sonnet携“极限推理”发布在即

目录一、GPT4.1加入网页端二、Claude 3.7 Sonnet携“极限推理”发布在即三、这项功能的关键特点1、双模式操作2、可视化思考过程3、可控的思考预算4、性能提升四、Claude制作SVG图像1、Prompt提示词模板2、demo：技术路线图**Prompt提示词：**3、甘特图4…...

编程日记 2025/5/22 11:02:15

Android 中使用通知(Kotlin 版)

1. 前置条件 Android Studio：确保使用最新版本（2023.3.1）目标 API：最低 API 21，兼容 Android 8.0（渠道）和 13（权限）依赖库：使用 WorkManager 和 Notificatio…...

编程日记 2025/5/19 8:28:42

在 Kotlin 中，什么是解构，如何使用？

在 Kotlin 中，解构是一种语法糖，允许将一个对象分解为多个独立的变量。这种特性可以让代码更简洁、易读，尤其适用于处理数据类、集合（如 Pair、Map）或其他结构化数据。 1 解构的核心概念解构通过定义 componentN()…...

编程日记 2025/5/20 4:27:43

apisix透传客户端真实IP（real-ip插件）

文章目录 apisix透传客户端真实IP需求和背景apisix real-ip插件为什么需要 trusted_addresses？安全架构的最佳实践示例场景apisix界面配置 apisix透传客户端真实IP 需求和背景当 APISIX 前端有其他反向代理（如 Nginx、HAProxy、云厂商的 LB&#xff…...

编程日记 2025/5/31 4:08:53

初学者如何用 Python 写第一个爬虫？

初学者如何用 Python 写第一个爬虫？ 一、爬虫的基本概念 （一）爬虫的定义爬虫，英文名为 Web Crawler，也被叫做网络蜘蛛、网络机器人。想象一下，有一个勤劳的小蜘蛛，在互联网这个巨大的蜘蛛网中…...

编程日记 2025/5/26 9:54:16

基于MNIST数据集的手写数字识别（CNN）

目录一，模型训练 1.1 数据集介绍 1.2 CNN模型层结构 1.3 定义CNN模型 1.4 神经网络的前向传播过程 1.5 数据预处理 1.6 加载数据 1.7 初始化 1.8 模型训练过程 1.9 保存模型二，模型测试 2.1 定义与训练时相同的CNN模型架构 2.2 图像的预处…...

编程日记 2025/5/28 4:05:54

QT6 源（103）篇三：阅读与注释 QPlainTextEdit，给出源代码

（10）关于文本处理的内容很多，来不及全面阅读、思考与整理。先给出类的继承图： （11）本源代码来自于头文件 qplaintextedit . h ： #ifndef QPLAINTEXTEDIT_H #define QPLAINTEXTEDIT_H#include &…...

编程日记 2025/5/22 22:53:11

yocto5.2开发任务手册-7 升级配方

此文为机器辅助翻译，仅供个人学习使用，如有翻译不当之处欢迎指正 7 升级配方随着时间的推移，上游开发者会为图层配方构建的软件发布新版本。建议使配方保持与上游版本发布同步更新。虽然有多种升级配方的方法，但您可能需要先…...

编程日记 2025/5/29 17:53:46

LangPDF: Empowering Your PDFs with Intelligent Language Processing

LangPDF: Empowering Your PDFs with Intelligent Language Processing Unlock Global Communication: AI-Powered PDF Translation and Beyond In an interconnected world, seamless multilingual document management is not just an advantage—it’s a necessity. LangP…...

编程日记 2025/5/22 8:53:37