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

力扣● 343. 整数拆分 ● 96.不同的二叉搜索树

● 343. 整数拆分

想不到,要勇于看题解。

关键在于理解递推公式。

1、DP数组及其下标的含义:dp[i]是分解i这个数得到的最大的乘积。

2、DP数组如何初始化:dp[0]和dp[1]都没意义,所以直接不赋值,初始化dp[2]=1即可。

3、递推公式:根据题目:给定一个正整数 n ,将其拆分为 k正整数 的和( k >= 2 )。可以分成两种情况:①n拆分成2个正整数的和。②n拆分成大于2个正整数的和。

①的话,dp[n]应该=j*(n-j)的最大值,②的话,dp[n]应该等于j*dp[n-j]的最大值。j是从1遍历到i-1,因为dp[n-j]是分解n-j这个数得到的最大的乘积,所以至少分解了2次,乘j就是至少分解了3次。

所以dp[n]应该取两种情况下的最大值,dp[n]=max(  j * ( n-j ), j * dp[n-j] )。这个dp[n]只是n包含j的时候分解的最大值,和前面的n包含1……j-1的时候分解的最大值没有联系起来,所以这个式子还是不对的。

因此dp[n]还要和自己比较,和之前的j对应的最大值(也就是最近一次更新的dp[n]比较),最终才是最大值。

根据公式得到从2到10的最大乘积如下:

校验发现正确。

4、遍历顺序:

当然是从左到右从小到大,小的数统计好了,大的数就靠小的数的最大乘积来统计。i初始化了2,所以应该是从3到n,注意下标是对应的,最后就是返回dp[n]。对于j,一般认为从1到i-1,比如4,分解2个的话是1和3,2和2,3和1。j是1,2就统计到了所有的乘积,因为后面的是对称的,所以其实从1到i/2就行。发现分解成2个以上的话也是到i/2之前就能统计到最大值,具体原因还不知道。

5、打印DP数组。
打印如上图,发现没错。

代码:

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[2]=1;             //初始化for(int i=3;i<=n;++i){for(int j=1;j<=i/2;++j){dp[i]=max({dp[i],j*(i-j),j*dp[i-j]});    //考虑k=2和k>2的情况,更新dp[i]}}return dp[n];}
};

● 96.不同的二叉搜索树

n=3的时候,分为以1为头结点、以2为头结点和以3为头结点三种情况。所以对于所有n,都是如此。

n=3的时候,数量是下面三个数量相加:

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量;

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量;

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量。

那么令dp[i]就是i个节点组成的二叉搜索树的数量,对于所有n,数量是下面n个数量相加:

元素1为头结点搜索树的数量=dp[n-1] * dp[0];

……

元素n为头结点搜索树的数量 = dp[0] * dp[n-1]。

1.dp[i]含义:i个节点组成的二叉搜索树的数量

2.递推公式:dp[i]=\sum_{j=0}^{n-1}dp[j]dp[n-1-j]

3.初始化:dp[0]=1,dp[1]=1;注意dp[0]是1,空树也是一棵搜索树。

4.遍历顺序:同样的由小推大。

代码:

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=0;j<i;++j){       //求和公式dp[i]+=dp[j]*dp[i-1-j]; }}return dp[n];}
};

相关文章:

力扣● 343. 整数拆分 ● 96.不同的二叉搜索树

● 343. 整数拆分 想不到&#xff0c;要勇于看题解。 关键在于理解递推公式。 1、DP数组及其下标的含义&#xff1a;dp[i]是分解i这个数得到的最大的乘积。 2、DP数组如何初始化&#xff1a;dp[0]和dp[1]都没意义&#xff0c;所以直接不赋值&#xff0c;初始化dp[2]1即可。…...

游戏同步+游戏中的网络模块

原文链接&#xff1a;游戏开发入门&#xff08;九&#xff09;游戏同步技术_游戏数据同步机制流程怎么开发-CSDN博客 游戏开发入门&#xff08;十&#xff09;游戏中的网络模块_游戏开发组网-CSDN博客 3.同步技术的基本常识&#xff1a; a.同步给谁&#xff1f;某个用户&…...

【03】逆序数组

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 一、逆序函数是什么&#xff1f; 二、逆序函数原码 1.直接逆序 2.创建临时数组逆序 三、结言 &#x1f4a5;一、逆序函数是什么&#xff1f; 示例&#xff1a;输入1 4 …...

基于Prony算法的系统参数辨识matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 Prony算法是一种用于信号处理和系统辨识的经典方法&#xff0c;特别适用于线性时不变系统&#xff08;LTI&#xff09;的频率响应分析以及模拟复指数信号序列。其…...

创建第一个React项目

React脚手架 npx create-react-app react-demonpx是直接从互联网网上拉最新的脚手架进行创建react 运行React项目 npm start若想找到Webpack配置文件 npm ejectReact的基本使用 基本步骤 导入react和react-dom vue 创建react元素 渲染react元素到页面中导入 import React…...

Redis篇之Redis持久化的实现

持久化即把数据保存到可以永久保存的存储设备当中&#xff08;磁盘&#xff09;。因为Redis是基于内存存储数据的&#xff0c;一旦redis实例当即数据将会全部丢失&#xff0c;所以需要有某些机制将内存中的数据持久化到磁盘以备发生宕机时能够进行恢复&#xff0c;这一过程就称…...

dpdk环境搭建和工作原理

文章目录 1、DPDK环境搭建1.1、环境搭建1.2、编译DPDK 2、DPDK工作原理 1、DPDK环境搭建 1.1、环境搭建 工具准备&#xff1a;VMware、ubuntu16.04。 &#xff08;1&#xff09;VMware添加两个网卡。桥接网卡作为 DPDK 运行的网卡&#xff0c;NAT 网卡作为 ssh 连接的网卡。 …...

接口测试实战--自动化测试流程

一、项目前期准备 常见项目软件架构: springMvc:tomcat里运行war包(在webapps目录下) springboot:java -jar xx.jar -xms(**) 运行参数 springCloud:k8s部署,使用kubectl create -f xx.yaml 接口自动化测试介入需越早越好,只要api定义好就可以编写自动化脚本; 某个…...

babylonjs中文文档

经过咨询官方&#xff0c;文档已经添加了开源协议。 基于目前babylonjs没有中文文档&#xff0c;为了打造更好的babylonjs生态圈 &#xff0c;特和小伙伴们翻译了官方文档。 相关链接: 欢迎加群&#xff1a;464146715 官方文档 中文文档 Babylonjs案例分享...

WordPress使用

WordPress功能菜单 仪表盘 可以查看网站基本信息和内容。 文章 用来管理文章内容&#xff0c;分类以及标签。编辑文章以及设置分类标签&#xff0c;分类和标签可以被添加到 外观-菜单 中。 分类名称自定义&#xff1b;别名为网页url链接中的一部分&#xff0c;最好别设置为中文…...

IDEA 2021.3激活

1、打开idea&#xff0c;在设置中查找Settings/Preferences… -> Plugins 内手动添加第三方插件仓库地址&#xff1a;https://plugins.zhile.io搜索&#xff1a;IDE Eval Reset 插件进行安装。应用和使用&#xff0c;如图...

进度条小程序

文章目录 铺垫回车换行缓冲区概述强制冲刷缓冲区 简单实现倒计时功能进度条小程序版本一实例代码效果展示分析 版本二 铺垫 回车换行 回车和换行是两个独立的动作 回车是将光标移动到当前行的最开始&#xff08;最左侧&#xff09; 换行是竖直向下平移一行 在C语言中&…...

K8S安装部署

常见的K8S安装部署方式 Minikube Minikube是一个工具&#xff0c;可以在本地快速运行一个单节点微型K8S&#xff0c;仅用于学习、预览K8S的一些特性使用。 部署地址&#xff1a;Install Tools | Kubernetes Kubeadm Kubeadm也是一个工具&#xff0c;提供kubeadm init和kube…...

AI大模型与小模型之间的“脱胎”与“反哺”(第一篇)

一、AI小模型脱胎于AI大模型&#xff0c;而AI小模型群又可以反哺AI大模型 AI大模型&#xff08;如GPT、BERT等&#xff09;通常拥有大量的参数和训练数据&#xff0c;能够生成或理解复杂的文本内容。这些大模型在训练完成后&#xff0c;可以通过剪枝、微调等方式转化为小模型&…...

C#学习总结

1、访问权限 方法默认访问修饰符&#xff1a;private 类默认访问修饰符&#xff1a;internal 类的成员默认访问修饰符&#xff1a;private 2、UserControl的使用 首先添加用户控件 使用时一种是通过代码添加&#xff0c;一种是通过拖动组件到xaml中...

计算机网络-网络互联

文章目录 网络互联网络互联方法LAN-LAN&#xff1a;网桥及其互连原理使用网桥实现LAN-LAN使用交换机扩展局域网使用路由器连接局域网 LAN-WANWAN-WAN路由选择算法非自适应路由选择算法自适应路由选择算法广播路由选择算法&#xff1a;分层路由选择算法 网络互联 网络互联是指利…...

免费的ChatGPT网站( 7个 )

ChatGPT 是由 OpenAI 公司研发的一款大型语言模型&#xff0c;它可以实现智能聊天、文本生成、语言翻译等多种功能。以下是 ChatGPT 的详细介绍&#xff1a; 智能聊天&#xff1a;ChatGPT 可以与用户进行自然语言对话&#xff0c;回答用户的问题&#xff0c;提供相关的信息和建…...

Opencv3.2 ubuntu20.04安装过程

##1、更新源 sudo add-apt-repository "deb http://security.ubuntu.com/ubuntu xenial-security main" sudo apt update##2、安装依赖库 sudo apt-get install build-essential sudo apt-get install cmake git libgtk2.0-dev pkg-config libavcodec-dev libavfor…...

OpenGL ES (OpenGL) Compute Shader 计算着色器是怎么用的?

OpenGL ES (OpenGL) Compute Shader 是怎么用的? Compute Shader 是 OpenGL ES(以及 OpenGL )中的一种 Shader 程序类型,用于在GPU上执行通用计算任务。与传统的顶点着色器和片段着色器不同,Compute Shader 被设计用于在 GPU 上执行各种通用计算任务,而不是仅仅处理图形…...

Python爬虫进阶:爬取在线电视剧信息与高级检索

简介&#xff1a; 本文将向你展示如何使用Python创建一个能够爬取在线电视剧信息的爬虫&#xff0c;并介绍如何实现更高级的检索功能。我们将使用requests和BeautifulSoup库来爬取数据&#xff0c;并使用pandas库来处理和存储检索结果。 目录 一、爬取在线电视剧信息 …...

Phi-3-mini-128k-instruct部署教程:基于vLLM的GPU显存优化方案(A10/A100实测)

Phi-3-mini-128k-instruct部署教程&#xff1a;基于vLLM的GPU显存优化方案&#xff08;A10/A100实测&#xff09; 1. 开篇&#xff1a;为什么选择Phi-3-mini-128k-instruct&#xff1f; 如果你正在寻找一个既轻量又强大的文本生成模型&#xff0c;那么Phi-3-mini-128k-instru…...

DeepSeek-VL2微调报错“AssertionError”终极解决:修改config.json里的topk_method参数

DeepSeek-VL2微调报错"AssertionError"终极解决方案&#xff1a;深入解析topk_method参数 当你满怀期待地准备微调DeepSeek-VL2这个强大的多模态大模型时&#xff0c;却在训练启动阶段遭遇了令人沮丧的"AssertionError"和"assert not self.training&q…...

4种SOCD模式深度解析:从键盘冲突到竞技优势的技术实现

4种SOCD模式深度解析&#xff1a;从键盘冲突到竞技优势的技术实现 【免费下载链接】socd SOCD cleaner tool for epic gamers 项目地址: https://gitcode.com/gh_mirrors/so/socd 在竞技游戏的世界里&#xff0c;每一次按键都可能是胜利与失败的分水岭。当玩家同时按下相…...

网盘下载加速工具:突破下载限制的直链提取技术详解

网盘下载加速工具&#xff1a;突破下载限制的直链提取技术详解 【免费下载链接】baiduyun 油猴脚本 - 一个免费开源的网盘下载助手 项目地址: https://gitcode.com/gh_mirrors/ba/baiduyun 你是否也曾遇到这样的情况&#xff1a;明明是自己辛苦上传的文件&#xff0c;下…...

Go gRPC 双向流通信实例

Go gRPC双向流通信实例解析 在现代分布式系统中&#xff0c;高效的双向通信是核心需求之一。gRPC作为Google开源的高性能RPC框架&#xff0c;支持双向流通信模式&#xff0c;允许客户端和服务端同时发送和接收多条消息。本文将以Go语言为例&#xff0c;介绍gRPC双向流通信的实…...

3个高效功能让Maccy成为macOS必备剪贴板管理器

3个高效功能让Maccy成为macOS必备剪贴板管理器 【免费下载链接】Maccy Lightweight clipboard manager for macOS 项目地址: https://gitcode.com/gh_mirrors/ma/Maccy Maccy是一款专为macOS设计的轻量级剪贴板管理器&#xff0c;能够记录复制历史&#xff0c;让用户轻松…...

Cursor试用限制如何解决?go-cursor-help工具三合一方案详解

Cursor试用限制如何解决&#xff1f;go-cursor-help工具三合一方案详解 【免费下载链接】go-cursor-help 解决Cursor在免费订阅期间出现以下提示的问题: Youve reached your trial request limit. / Too many free trial accounts used on this machine. Please upgrade to pro…...

为什么你的局域网速度慢?可能是集线器和交换机的区别没搞懂

为什么你的局域网速度慢&#xff1f;可能是集线器和交换机的区别没搞懂 家里或办公室的网络总是不给力&#xff1f;明明升级了宽带套餐&#xff0c;下载文件时却还是像蜗牛爬行&#xff1f;问题可能出在你忽略的网络设备选择上。许多用户至今仍在用早已淘汰的集线器&#xff08…...

Janus-Pro-7B开源大模型教程:HuggingFace模型路径本地加载实操

Janus-Pro-7B开源大模型教程&#xff1a;HuggingFace模型路径本地加载实操 1. 引言 如果你正在寻找一个既能看懂图片&#xff0c;又能根据文字生成图片的AI模型&#xff0c;那么Janus-Pro-7B绝对值得你花时间了解一下。这个模型最近在开源社区里挺火的&#xff0c;因为它把“…...

AHB-Lite时序图深度解读:那些官方文档没明说的‘潜规则’与设计陷阱

AHB-Lite时序图深度解读&#xff1a;那些官方文档没明说的‘潜规则’与设计陷阱 在数字IC设计中&#xff0c;AHB-Lite总线作为AMBA3.0协议家族的核心成员&#xff0c;以其简洁高效的架构成为片上系统互连的首选方案。然而&#xff0c;许多工程师在通过官方文档掌握基础协议后&a…...