代码随想录算法训练营第36期DAY43

news/2024/7/20 17:30:16/文章来源:https://blog.csdn.net/illuosion7/article/details/139298647

DAY43

343整数拆分

注意:当几个数的数值相近,乘积才会尽可能地大(好想:数一大一小,最大当然是自己乘以自己)

代码随想录官方题解:

  1. class Solution {
  2. public:
  3.     int integerBreak(int n) {
  4.     vector<intdp(n+1);
  5.     dp[0]=0,dp[1]=0;
  6.     dp[2]=1;
  7.     //求DP[i]
  8.     for(int i=3;i<=n;i++){
  9.         for(int j=1;j<=i/2;j++)
  10.         //i-1因为dp[0]没有意义
  11.         {
  12.             dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
  13.         }
  14.     }
  15.     return dp[n];
  16.     }
  17. };

力扣优质题解_Krahets:

太厉害了,数学方法:

  1. class Solution {
  2. public:
  3.     long long poww(int n,int index){
  4.         long long result=1;
  5.         while(index--) result*=n;
  6.         return result;
  7.     }
  8.     int integerBreak(int n) {
  9.     if(n<=3return n-1;
  10.     int mod=n%3,res=n/3;
  11.     if(mod==0return poww(3,res);
  12.     else if(mod==2return 2*poww(3,res);
  13.     else return 4*pow(3,res-1);
  14.     }
  15. };

力扣官方题解

这句话很好:由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积,因此可以使用动态规划来求解。这样DP动机就很可信了。

96不同的二叉搜索树

做完之后,完整地学习了卡特兰数。

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         vector<intdp(n+1);
  5.         dp[0]=1;
  6.         dp[1]=1;
  7.         for(int i=2;i<=n;i++){
  8.             for(int j=1;j<=i;j++)
  9.             dp[i]+=dp[j-1]*dp[i-j];
  10.         }
  11.         return dp[n];
  12.     }
  13. };

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         //C0=1;
  5.         long long C=1;
  6.         for(int i=0;i<n;i++){
  7.             C=C*2*(2*i+1)/(i+2);
  8.         }
  9.         return (int) C;
  10.     }
  11. };

卡特兰数学习

公式:

手写运算用:

编程解题用:

对应代码:

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         //C0=1;
  5.         long long C=1;
  6.         for(int i=0;i<n;i++){
  7.             C=C*2*(2*i+1)/(i+2);
  8.         }
  9.         return (int) C;
  10.     }
  11. };

参考资料:

  1. 《A First Course in Discrete Mathematics》
  2. 算法学习笔记(11):[卡特兰数 (Catalan)](https://zhuanlan.zhihu.com/p/609104268)
  3. Leetcode官方题解——96.不同的二叉搜索树

(https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/)

  1. Up-Right问题

简单 2n选n。

  1. Up-Right问题——不抵达对角线上方

真正引出了卡特兰数,具体分析及推导见《A First Course in Discrete Mathematics》

  1. Cn 表示2n长的序列,有n个0(right),n个1(up),在任意n(each stage),1的数量不超过0的数量。
  2. 由n对 左 右 括号构成的合法的括号序列数。

其实和3一样了。就是右括号数永远不超过左括号数。

  1. 一个栈(无穷大)的进栈顺序1,2,...,n有多少个不同的出栈顺序?

只要有进栈,就产生一个左括号;只要有出栈,就产生一个右括号。(2n长的序列)

那么每阶段右括号数量不超过左括号数量。卡特兰数

  1. N个节点可以构造出多少个不同的二叉树?

直接看图:

  1. 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数?

课本上也有,

看图:

  1. N个 +1 和 -1 构成2N项a1,a2,...,an,其任意前缀和a1+a2+..+ak非负 的序列数量个数。

-1别超过1就行了。

  1. 在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?

作者说的很好,看图:

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

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

相关文章

【Vue】input框自动聚焦且输入验证码后跳至下一位

场景&#xff1a;PC端 样式&#xff1a; <div class"verification-code-input"><input v-model"code[index]" v-for"(_, index) in 5" :key"index" type"text" maxlength"1" input"handleInput(i…

Centos7时区设置及手动修改时间

一、修改系统时区 1、查看时区命令 timedatectl 2、设置时区命令 #下面将时区设置为上海时区 timedatectl set-timezone Asia/Shanghai 3、查看时区看一下新时区有没有生效 timedatectl 二、手动修改系统时间 修改系统时间 date -s "2023-12-25 16:05:10" 查…

【易错题】数据可视化基础练习题(30道选择题)#CDA Level 1

本文整理了数据可视化基础知识相关的练习题&#xff0c;共30道&#xff0c;适用于想巩固数据可视化知识的同学&#xff0c;也可作为备考CDA一级的补充习题。来源&#xff1a;如荷学数据科学题库&#xff08;技术专项-可视化&#xff09;。 1&#xff09; 2&#xff09; 3&…

【AI大模型】如何让大模型变得更聪明?基于时代背景的思考

【AI大模型】如何让大模型变得更聪明 前言 在以前&#xff0c;AI和大模型实际上界限较为清晰。但是随着人工智能技术的不断发展&#xff0c;基于大规模预训练模型的应用在基于AI人工智能的技术支持和帮助上&#xff0c;多个领域展现出了前所未有的能力。无论是自然语言处理、…

【ORB_SLAM系列3】—— 如何在Ubuntu18.04中使用自己的单目摄像头运行ORB_SLAM3(亲测有效,踩坑记录)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、ORB_SLAM3源码编译二、ORB_SLAM3实时单目相机测试1. 查看摄像头的话题2. 运行测试 三. 运行测试可能的报错1. 报错一(1) 问题描述(2) 原因分析(3) 解决 2. …

工控一体机7寸显示器电容触摸屏(YA131607JK)产品规格说明书

如果您对工控一体机有任何疑问或需求&#xff0c;或者对如何集成工控一体机到您的业务感兴趣&#xff0c;可移步控芯捷科技。 一、硬件功能介绍 YA131607JK产品介绍&#xff1a; YA131607JK 搭载 Android10 主流操作系统&#xff0c;具有系统版本更高、占用内存更低、运行效率…

HTML-JavaWeb

目录 1.标题排版 2.标题样式 ​编辑 ​编辑 小结 3.超链接 4.正文排版 ​编辑​编辑​编辑5.正文布局 6.表格标签 7.表单标签 8.表单项标签 1.标题排版 ● 图片标签 :< img> src:指定图像的ur1(绝对路径/相对路径) width:图像的宽度(像素/相对于父元素的百…

linux开发之设备树五、设备树描述中断实践

设备树是基于设备总线模型的&#xff08;platform&#xff09; 1、添加节点 假设中断引脚为&#xff1a;GPIO0_B5 下面使用设备树来描述它 1、写节点&#xff0c;起节点名字 这里用了ft5x06的触摸芯片&#xff0c;然后I2C的地址为38 2、为节点添加属性 首先添加compatible…

抖店除了商品卡流量还有什么流量?

我是王路飞。 随着抖音开放商品卡流量&#xff0c;它一度成为去年最大热的玩法。 包括到现在&#xff0c;还有很多新手对其有一种莫名的信任感&#xff0c;只想做商品卡流量。 那么抖店除了商品卡流量还有什么流量玩法呢&#xff1f;哪种比较容易出单呢&#xff1f; 今天就…

Facebook:连接世界,畅游社交之旅

作为全球最大的社交平台之一&#xff0c;Facebook不仅仅是一个网站&#xff0c;更是一个连接世界的桥梁&#xff0c;让人们可以轻松地与全球各地的朋友、家人和同事保持联系&#xff0c;分享生活、交流想法&#xff0c;畅游社交的无边界之旅。本文将带领读者探索Facebook的魅力…

【问题解决】pycharm中添加python interpreter报错 conda excutable is no found

选择安装目录下的conda.bat文件&#xff0c;然后点击“Load Environments”按钮&#xff0c;然后在列表中选择conda环境即可。

C++笔记:Hash Function 散列函数

1. Hash Function 散列函数 简单的Hash实现&#xff1a; class CustomerHash { public:size_t operator()(const Customer& c) const {return hash<std::string>()(c.fname) // first namehash<std::string>()(c.lname) // last namehash<long>()(…

嵌入式学习记录5.18(多点通信)

一、套接字属性设置相关函数 #include <sys/types.h> /* See NOTES */#include <sys/socket.h>int getsockopt(int sockfd, int level, int optname,void *optval, socklen_t *optlen);int setsockopt(int sockfd, int level, int optname,const void *op…

量化交易入门:如何在QMT中配置Python环境,安装第三方依赖包

哈喽,大家好,我是木头左! 引言 QMT,作为量化交易系统中的佼佼者,以其强大的功能和灵活的操作性,受到了广大投资者的青睐。但是,对于很多新手来说,如何在QMT中配置Python环境,安装第三方依赖包,却是一个让人头疼的问题。本文将从零开始,手把手教你如何在QMT中配置Py…

股票交易vip快速通道有什么门槛?vip交易通道的开通流程!

证券公司的VIP通道通常是为了满足高端客户或高频交易客户的需求而设立的&#xff0c;提供更快速、更便捷的交易服务。证券公司VIP通道适用于有追涨停板需求的投资者&#xff0c;以及一些喜爱高频交易的投资者&#xff0c;总的来说就是快速&#xff0c;在交易主机排队靠前。 VI…

MySQL8报错Public Key Retrieval is not allowedz 怎么解决?

问题描述 当我们使用数据库管理工具连接mysql8的时候&#xff0c;可能遇到报错&#xff1a; Public Key Retrieval is not allowed 解决办法 1、在连接属性中配置allowPublicKeyRetrieval设置为true 2、在连接URL中加上配置allowPublicKeyRetrieval为true

Discourse 编辑没有办法显示更多的 JS 错误

Priority/Severity: High Platform: 3.3.0.beta3-dev UI bugs Description: 昨天升级的时到最新版本的时候就发现有这个错误&#xff0c;是 JS 的错误。 发了一个帖子到官方的网站上&#xff0c;官方说可能是插件的问题。 但是我们实在是没有安装什么插件呀&#xff1f; 官方…

uniapp一些问题解决

1.按钮边框如何去除&#xff1f; 参考博主&#xff1a;微信小程序按钮去不掉边框_微信小程序button去掉边框-CSDN博客文章浏览阅读1k次。最近在学uni-app&#xff0c;顺便自己写个小程序。左上角放了个button&#xff0c;可边框怎么也去不掉…原来微信小程序的按钮要去掉边框要…

软件游戏找不到xinput1_3.dll如何修复?分享几种有效的解决方法

当您在使用电脑过程中遇到系统提示“xinput1_3.dll文件丢失”时&#xff0c;这可能会导致某些游戏或应用程序无法正常运行&#xff0c;因为xinput1_3.dll是与DirectX相关的一个重要动态链接库文件&#xff0c;主要负责处理游戏控制器输入。为了解决这个问题&#xff0c;我通过查…

期权具体怎么交易详细的操作流程?

期权就是股票&#xff0c;唯一区别标的物上证指数&#xff0c;会看大盘吧&#xff0c;交易两个方向认购做多&#xff0c;认沽做空&#xff0c;双向t0交易&#xff0c;期权具体交易流程可以理解选择方向多和空&#xff0c;选开仓的合约&#xff0c;买入开仓和平仓没了&#xff0…