代码随想录训练营第34天|dp前置转移
62. 不同路径
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,1));for(int i=1; i<m;i++){for(int j=1; j<n; j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
};
dp[i][j]:运动至(i,j)的方案数
转移方程:可由上/左两个方向转移而来,累加不同的方案数。
63. 不同路径 II
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int row=obstacleGrid.size();int col=obstacleGrid[0].size();vector<vector<int>> dp(row, vector<int>(col,0));for(int j=0; j<col&&obstacleGrid[0][j]==0; j++)dp[0][j]=1;for(int i=0; i<row&&obstacleGrid[i][0]==0; i++)dp[i][0]=1;for(int i=1; i<row; i++){for(int j=1; j<col; j++){if(obstacleGrid[i][j]==0){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[row-1][col-1];}
};
dp[i][j]:运动至(i,j)的方案数
转移方程:
- 没有障碍物的情况下,可以由上或左两个方向转移而来;
- 有障碍物的情况只能取0,表示没有方案,不可达。
343. 整数拆分
class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1,0);dp[2]=1;for(int i=3; i<=n; i++){for(int j=1; j<i; j++){dp[i]=max({dp[i],dp[i-j]*j,(i-j)*j});}}return dp[n];}
};
dp[i]:拆分i可以达到的最大乘积
转移方程:给定i,可能由任何一个前置的j拆分而来,对于剩下的部分(i-j)由两种选择:
- 1.不拆,此时拆分乘积为 (i-j)*j
- 2.拆,此时拆分乘积为 dp[i-j]*j
根据dp的定义对二者取最大。
另外,dp[1]初始化为0,表示拆分1的情况是非法的,这样取max后自然被过滤掉。
96. 不同的二叉搜索树
class Solution {
public:int numTrees(int n) {vector<int> dp(n+1,0);dp[0]=1;for(int i=1; i<=n; i++){for(int j=1; j<=i; j++){dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
};
dp[i]:给定节点数i,可构造的搜索树数目
转移方程:给定节点数i,搜索树的根可以取前置任一节点:1、2……i,dp[i]累加不同情况而来。选定j(j<=i)作为根:
- 左子树节点数为:j-1,左子树的形态数目:dp[j-1]。
- 右子树节点数为:i-(j+1)+1,形态数:dp[i-j],不需要关注每个节点具体数值的差异。
- 根据乘法原理,由左右子树个数得到整个树的形态数:dp[j-1]*dp[i-j]。
相关文章:
代码随想录训练营第34天|dp前置转移
62. 不同路径 class Solution { public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,1));for(int i1; i<m;i){for(int j1; j<n; j){dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];} }; dp[i][j]:运动至(i,j)的方…...
乐观锁、悲观锁
一、悲观锁 悲观锁 (Pessimistic Locking),具有强烈的独占和排他特性。它指的是对数据被外界修改持保守态度。因此,在整个执行过程中,将处于锁定状态。所以,悲观锁是一种悲观思想,它总认为最坏的情况可能会出现&#x…...
Java客户端SpringDataRedis(RedisTemplate使用)
文章目录 ⛄概述⛄快速入门❄️❄️导入依赖❄️❄️配置文件❄️❄️测试代码 ⛄数据化序列器⛄StringRedisTemplate⛄RedisTemplate的两种序列化实践方案总结 ⛄概述 SpringData是Spring中数据操作的模块,包含对各种数据库的集成,其中对Redis的集成模…...
wsl2桥接网络 ubuntu到弃坑到又跳坑
搜索Hyper-V image.png 如下图进入虚拟交换机管理器 image.png image.png C:\Users\Administrator下存放 ; 这是 WSL 2 的配置文件 [wsl2] processors4 ; 设置 WSL 2 可以使用的最大 CPU 核心数为 4,自行修改 memory4GB …...
WIFI路由器的套杆天线简谈
❝本次推文简单介绍下WIFI路由器的套杆天线。 路由器天线 路由器在这个万物互联的时代,想必大家对其都不陌生。随着科技的发展,常用的路由器上的天线也越来越多,那么问题来了:天线越多,信号越好吗?路由器…...
希尔排序(C语言实现)
目录 1.希尔排序( 缩小增量排序 ) 2.动图 编辑 3.代码实现 预排序实现 子序列排列实现 单趟排序实现 对整组数进行子排序 希尔排序代码 代码测试 时间复杂度分析 希尔排序的特性总结: 1.希尔排序( 缩小增量排序 ) 基本思想: 1.先选定一个…...
LLVM 中的Value、User、Use设计
概述 LLVM是一个强大的编译器基础设施,提供了一套丰富的库,用于构建编译器的前端和后端。在LLVM中,Value、User和Use是几个核心的概念,它们之间有着紧密的关系 Value Value是LLVM中表示所有可计算的值的基类,例如常…...
C++智能指针入门教程(C++11)
智能指针 1.定义 C中的智能指针是一种用于自动管理动态分配的内存的模板类,它们通过封装原始指针来提供自动的内存管理功能,从而避免了内存泄漏和悬挂指针等问题。C标准库中提供了几种智能指针类型,其中最常用的是std::unique_ptr、std:…...
常用工具推荐!分享7款AI论文修改软件工具网站
在当今学术研究和写作领域,AI论文修改软件工具已经成为了不可或缺的助手。这些工具不仅能够帮助研究人员提高写作效率,还能确保论文的质量和原创性。以下是七款值得推荐的AI论文修改软件工具网站,其中特别推荐千笔-AIPassPaper。 1. 千笔-AI…...
怎么解除BitLocker对磁盘的加密?
BitLocker是一种Windows操作系统内置的加密功能,用于保护用户的数据安全。它通过对整个磁盘进行加密,防止数据被未经授权的用户访问。BitLocker主要用于保护笔记本电脑和台式机中的重要数据,尤其是在设备丢失或被盗的情况下。怎么解除BitLock…...
群晖使用Docker部署WPS Office并实现异地使用浏览器制作办公文档
文章目录 前言1. 本地环境配置2. 制作本地分享链接3. 制作公网访问链接4. 公网ip地址访问您的分享相册5. 制作固定公网访问链接 前言 想象一下这个场景:如果遇到周末紧急需要改方案,但团队成员都在各自家中,这个时候如果大家能够轻松访问这个…...
Unity3d 以鼠标位置点为中心缩放视角(正交模式下)
思路整理: 缩放前: 缩放后: 记录缩放前鼠标的屏幕坐标 A,计算鼠标位置对应的世界坐标 A_world 缩放完成后,根据当前屏幕下A所对应的世界坐标A1_world 计算A1_world 和 A_world 的偏移量 移动摄像机 代码ÿ…...
Git清除某文件所有历史提交记录
一、软件要求 1.1 软件版本要求 git > 2.22.0python3 > 3.5 1.2 辅助插件 git filter-repo Linux/macOS # Debian/Ubuntu 系统 # 或使用 pip 安装pip install git-filter-repo sudo apt install git-filter-repo Windows pip install git-filter-repo二、操作步骤…...
jacoco生成单元测试覆盖率报告
前言 单元测试是日常编写代码中常用的,用于测试业务逻辑的一种方式,单元测试的覆盖率可以用来衡量我们的业务代码经过测试覆盖的比例。 目前市场上开源的单元测试覆盖率的java插件,主要有Emma,Cobertura,Jacoco。具体…...
【CSS Tricks】如何做一个粒子效果的logo
效果展示 代码展示 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>粒子效果Logo</title>…...
如何使用ssm实现基于Javaweb的网上花店系统的设计与实现
TOC ssm653基于Javaweb的网上花店系统的设计与实现jsp 研究背景 自计算机发展以来给人们的生活带来了改变。第一代计算机为1946年美国设计,最开始用于复杂的科学计算,占地面积、开机时间要求都非常高,经过数十几的改变计算机技术才发展到今…...
Elastic 的 OpenTelemetry PHP 发行版简介
作者:Pawel Filipczak 宣布 OpenTelemetry PHP 的 Elastic 发行版的第一个 alpha 版本。在本篇博文中了解使用 OpenTelemetry 来检测 PHP 应用程序是多么简单。 我们很高兴推出 OpenTelemetry PHP 的 Elastic Distribution 的第一个 alpha 版本。在这篇文章中&…...
TCP 和 UDP 协议的区别?
参考TCP 和 UDP的区别_tcp和udp的区别-CSDN博客...
【PHP】使用thinkphp5查询最大值时,把varchar类型字段转换成数字
有时候我们需要把carchar类型的字段进行聚合函数运运行(max、min、avg),但是如果直接用聚合函数,得到的结果是错误的,因为varchar字段是字符串,无法直接使用聚合函数,所以需要把varchar字段转换…...
Java 正则表达式详解
正则表达式 (Regular Expression,简称 regex) 是一种强大的文本处理工具,可以用来匹配、搜索和替换文本中的特定模式。在 Java 中,正则表达式由 java.util.regex 包提供支持。 1. 理解正则表达式语法 正则表达式使用特殊的字符和符号来定义…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
