代码随想录算法训练营29期Day41|LeetCode 343,96

  文档讲解:整数拆分  不同的二叉搜索树

343.整数拆分

题目链接:https://leetcode.cn/problems/integer-break/description/

思路:

       题目要求我们拆分n,拆成k个数使其乘积和最大,然而题目中并没有给出k,所以拆分个数不能作为维度来使用。

       那我们就设dp[i]表示拆分i能获得的最大乘积,则最终答案为dp[n],同时初始状态为dp[1]=0,dp[2]=1

       那我们在求dp[i]时,可以枚举两个数的和为i。即枚举一个j,j从1到i-1,则获得i=j+(i-j)

       则dp[i]=max(dp[i],j*dp[i-j]);

       但这种写法少考虑了一种情况,就是j*(i-j),即dp[i]直接拆分成两个数。

       因此总的状态转移方程为:dp[i]=max(dp[i],j*max(i-j,dp[i-j]));

       按照上述方法,先枚举i,再枚举j,最后就能求出dp[n],即解决这道题目了。

核心代码:

class Solution {
public:int integerBreak(int n) {int dp[60];//dp[i]表示和为i时可以获得的最大乘积for(int i=1;i<=n;i++) dp[i]=i-1;dp[1]=1;for(int i=3;i<=n;i++)for(int j=1;j<i;j++){dp[i]=max(dp[i],j*max(i-j,dp[i-j]));}return dp[n];}
};

96.不同的二叉搜索树

题目链接:https://leetcode.cn/problems/unique-binary-search-trees/description/

思路:

       题目给我们一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种。

       其实值是多少并不重要,重点是我们知道每个数都不相同,这就不影响我们的结果。

       很明显我们能够意识到,n个点要由更少的点来推,所以我们朴素的想法是先设状态:设dp[n]表示有n个点时不同的二叉搜索树的个数。初始状态为dp[0]=1,dp[1]=1。假设现在我们知道dp[1]至dp[n-1]了,下面考虑怎么求dp[n]:

       什么时候树不同呢?根节点不同时树一定不同。因此我们依次让1到n为根节点,求其不同二叉搜索树个数即可:

       1为根节点时,左子树有n-1个点,右子树有0个点,不同的二叉搜索树个数为dp[n-1]*dp[0]。

       2为根节点时,左子树有n-2个点,右子树有1个点,不同的二叉搜索树个数为dp[n-2]*dp[1]。

       ……

       n为根节点时,左子树有0个点,右子树有n-1个点,不同的二叉搜索树个数为dp[0]*dp[n-1]。

       统计上面n种情况的和,即可求出dp[n]。同时根据上面的分析我们也可以得到规律:

       dp[n]=\sum_{0}^{n-1}{dp[j]*dp[n-1-j]}

       根据上述状态转移方程和初始状态,枚举推导即可。

核心代码:

class Solution {
public:int numTrees(int n) {int dp[20];memset(dp,0,sizeof(dp));dp[0]=dp[1]=1;for(int i=2;i<=n;i++)for(int j=0;j<i;j++) dp[i]+=dp[j]*dp[i-j-1];return dp[n];}
};

今日总结

        今日学习时长2h,题难度还算可以,都做出来了。

        接着冲击八股文。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/250536.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

影院购票|电影院订票选座小程序|基于微信小程序的电影院购票系统设计与实现(源码+数据库+文档)

电影院订票选座小程序目录 目录 基于微信小程序的电影院购票系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户功能实现 2、管理员功能实现 &#xff08;1&#xff09;影院信息管理 &#xff08;2&#xff09;电影信息管理 &#xff08;3&#xff09;已…

算法学习——华为机考题库6(HJ36 - HJ40)

算法学习——华为机考题库6&#xff08;HJ36 - HJ40&#xff09; HJ36 字符串加密 描述 有一种技巧可以对数据进行加密&#xff0c;它使用一个单词作为它的密匙。下面是它的工作原理&#xff1a;首先&#xff0c;选择一个单词作为密匙&#xff0c;如TRAILBLAZERS。如果单词中…

链表——C语言——day17

链表 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。在用数组存放数据时&#xff0c;必须事先定义固定的长度&#xff08;即元素个数&#xff09;。链表则没有这种缺点&#xff0c;它根据需要开辟内存单元。 链表有一个“头指针“变量&#xff0c;图中…

kubekey网页版安装k8s集群操作流程

kubekey可以一键拉起k8s集群并完成kubesphere的部署&#xff0c;以后kubekey简称kk。kk 3.2版本以前都是在宿主机上完成对应的创建集群、添加节点、升级等操作的&#xff0c;3.2版本后开始往页面操作的方向演进&#xff0c;kk 3.2版本现在还是alpha&#xff0c;所以不推荐在生产…

fastadmin后台自定义按钮和弹窗

工具栏自定义按钮-ajax请求 前端代码 1.在对应模块的模板文件index.html添加自定义按钮&#xff0c;注意按钮要添加id以绑定点击事件 <div class"panel panel-default panel-intro">{:build_heading()}<div class"panel-body"><div id&qu…

STM32通用定时器、计数器

时间记录&#xff1a;2024/1/30 一、时钟介绍&#xff08;TIM2-TIM5&#xff09; &#xff08;1&#xff09;通用定时器时钟频率介绍 内部时钟AHB为72MHz&#xff0c;经过APB1预分频器2分频变为36MHz&#xff0c;TIMxClk定时器时钟由时钟树可以看出&#xff0c;如果APB1预分…

C#,雅各布斯塔尔—卢卡斯(Jacobsthal Lucas Number)的算法与源代码

1 雅各布斯塔尔序列 雅各布斯塔尔序列是一个与斐波那契序列类似的加法序列&#xff0c;由递归关系JnJn-12Jn-2定义&#xff0c;初始项J00&#xff0c;J11。序列中的一个数字称为雅可布沙尔数。它们是卢卡斯序列Un&#xff08;P&#xff0c;Q&#xff09;的一种特殊类型&#x…

微软Office Plus与WPS Office的较量:办公软件市场将迎来巨变?

微软Office Plus在功能表现上远超WPS Office&#xff1f; 微软出品的Office套件实力强劲&#xff0c;其不仅在办公场景中扮演着不可或缺的角色&#xff0c;为用户带来高效便捷的体验&#xff0c;而且在娱乐生活管理等多元领域中同样展现出了卓越的应用价值 作为中国本土办公软…

IO多路复用机制——select、poll、epoll的原理和区别

select&#xff0c;poll&#xff0c;epoll都是IO多路复用的机制。I/O多路复用就通过一种机制&#xff0c;可以监视多个描述符&#xff0c;一旦某个描述符就绪&#xff08;一般是读就绪或者写就绪&#xff09;&#xff0c;能够通知程序进行相应的读写操作。但select&#xff0c;…

西瓜书学习笔记——k近邻学习(公式推导+举例应用)

文章目录 算法介绍实验分析 算法介绍 K最近邻&#xff08;K-Nearest Neighbors&#xff0c;KNN&#xff09;是一种常用的监督学习算法&#xff0c;用于分类和回归任务。该算法基于一个简单的思想&#xff1a;如果一个样本在特征空间中的 k k k个最近邻居中的大多数属于某个类别…

使用ngrok内网穿透

没有服务器和公网IP&#xff0c;想要其他人访问自己做好的网站&#xff0c;使用这款简单免费的内网穿透小工具——ngrok&#xff0c;有了它轻松让别人访问你的项目~ 一、下载ngrok 官网地址&#xff1a;ngrok | Unified Application Delivery Platform for Developers&#x…

IP定位在社交行业应用

网络社交正成为当下最便捷的交友方式。社交服务平台使用IP地址数据服务&#xff0c;解析用户的地理位置和网络环境等信息&#xff0c;支撑精准配对和用户推荐&#xff0c;帮助用户在海量的网络社交用户中寻找性情相投的好友&#xff0c;建立有价值的社交关系。 匹配目标好友 通…

未来电话呼叫技术的全球影响与社会变革----云微呼

随着科技的快速发展和全球通信网络的日益完善&#xff0c;未来电话呼叫技术将在全球范围内产生深远的影响&#xff0c;并引发社会结构、经济模式和文化交流等多个方面的变革。以下将更详细地探讨未来电话呼叫技术可能带来的全球影响与社会变革&#xff1a; 通信普及与数字鸿沟缩…

人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型23-pytorch搭建生成对抗网络(GAN):手写数字生成的项目应用。生成对抗网络&#xff08;GAN&#xff09;是一种强大的生成模型&#xff0c;在手写数字生成方面具有广泛的应用前景。通过生成…

Mysql学习记录补充

索引 在无索引情况下&#xff0c;就需要从第一行开始扫描&#xff0c;一直扫描到最后一行&#xff0c;我们称之为 全表扫描&#xff0c;性能很低。 如果我们针对于这张表建立了索引&#xff0c;假设索引结构就是二叉树&#xff0c;那么也就意味着&#xff0c;会对age这个字段…

MySQL EXPLAIN查询执行计划

EXPLAIN 可用来查看SQL执行计划&#xff0c;常用来分析调试SQL语句&#xff0c;来使SQL语句达到更好的性能。 1 前置知识 在学习EXPLAIN 之前&#xff0c;有些基础知识需要清楚。 1.1 JSON类型 MySQL 5.7及以上版本支持JSON数据类型。可以将数组存为JSON格式的字符串&#…

【Java 数据结构】排序

排序算法 1. 排序的概念及引用1.1 排序的概念1.2 常见的排序算法 2. 常见排序算法的实现2.1 插入排序2.1.1 直接插入排序2.1.2 希尔排序( 缩小增量排序 ) 2.2 选择排序2.2.1 直接选择排序2.2.2 堆排序 2.3 交换排序2.3.1冒泡排序2.3.2 快速排序2.3.3 快速排序非递归 2.4 归并排…

搜索引擎评价指标及指标间的关系

目录 二分类模型的评价指标准确率(Accuracy,ACC)精确率(Precision,P)——预测为正的样本召回率(Recall,R)——正样本注意事项 P和R的关系——成反比F值F1值F值和F1值的关系 ROC&#xff08;Receiver Operating Characteristic&#xff09;——衡量分类器性能的工具AUC&#xff…

【AI_Design】Midjourney学习笔记

目录 后缀解析Promot合格使用prompt关键词描述 关键词化合作用关键词网站推荐 联合Chatgpt使用总结 后缀解析 –ar&#xff1a;宽高比设置–c&#xff1a;多样性设置&#xff08;数值0-100&#xff0c;默认值0&#xff09;–s&#xff1a;风格化设置&#xff08;数值0-1000&am…

电脑怎么录屏?打造专业级视频内容!

随着科技的进步&#xff0c;电脑已经深入到我们的日常生活和工作中。而在这个数字时代&#xff0c;录制屏幕内容变得日益重要。无论是制作教程、分享游戏技巧&#xff0c;还是记录重要的演示&#xff0c;录屏都是一个不可或缺的功能。可是电脑怎么录屏呢&#xff1f;本文将深入…