代码随想录算法训练营第41天 | 343:整数拆分, 96:不同的二叉搜索树

Leetcode - 343:整数拆分

题目:

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

笔记:

按照动规五部曲来思考:

(1)确定dp数组含义:

dp[i]表示拆分整数i的最大成绩和

(2)初始化dp数组:

dp[0] = 0,dp[1] = 1, dp[2] = 1

(3)确定状态转移方程:

由于我们在拆分的时候做选择:一个是我们可以选择两个数来做比较,一个我们可以将被减数在做拆分用被减数的最大字元素乘积,也就是我们可以选择拆掉被减数或者不拆被减数:

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

(3)遍历顺序:

从小到大遍历即可

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

这里我们需要注意的是第二个max才是体现我们动态规划思想的重要一步。

为什么不拆分j呢;因为j的拆分已经在第一层for循环求过了。

Leetcode - 96:不同的二叉搜索树

题目:

给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

笔记:

这道题是真的难,

(1)确定dp数组含义:dp[i]表示i个元素的二叉搜索树的种类。

(2)初始化,dp[0] = 1

(3)状态转移方程:这里我们用到了两层循环,外层循环是求目标数,内层循环是选取不同的节点作为头结点,各自的搜索树数量。以m为头结点的搜索树,其左子树有m-1个元素,其右节点有n-m个(减去头节点)。然后因为是求组合数所以两者相乘即得。

dp[i] += dp[j - 1] * dp[i - j];

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];
    }
};

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

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

相关文章

WinForm_初识_事件_消息提示

文章目录 WinForm开发环境的使用软件部署的架构B/S 架构应用程序C/S 架构应用程序 创建 Windows 应用程序窗口介绍查看设计窗体 Form1.cs 后台代码窗体 Form1.cs窗体的常用属性 事件驱动机制事件的应用事件的测试测试事件的级联响应常用控件的事件事件响应的公共方法 消息提示的…

入门必读!如何实现适老化设计?大广赛题目解析!

早在 2021 年 4 月工业和信息化部办公厅发布了《关于进一步落实互联网应用老化和无障碍改造专项行动的通知》。根据联合国经济和社会事务部发布的2022年世界人口展望报告&#xff0c;全球人口展望报告&#xff0c;全球人口展望报告 65 预计2022年以上人口比例将达到2022年以上年…

2021-08-06

yarn的简介&#xff1a; Yarn是facebook发布的一款取代npm的包管理工具。 yarn的特点&#xff1a; 速度超快。 Yarn 缓存了每个下载过的包&#xff0c;所以再次使用时无需重复下载。 同时利用并行下载以最大化资源利用率&#xff0c;因此安装速度更快。超级安全。 在执行代码…

哈希表(Hash Table) -- 用数组模拟--字符串前缀哈希

本文用于个人算法竞赛学习&#xff0c;仅供参考 目录 一.什么是哈希表 二.哈希函数中的取模映射 三.拉链法&#xff08;数组实现&#xff09; 四.拉链法模板 五.开放寻址法 六.开放寻址法模板 七.字符串前缀哈希 九.字符串前缀哈希 模板 十.题目 一.什么是哈希表 哈希表&…

python print用法

1.输出字符串换行 输出结果会换行&#xff0c;默认自带换行 print(111) print(0) 2.末尾插入字符串或去除换行 末尾只能插入字符串&#xff0c;不能是其他类型 print(111,end0) print(0) 3.变量&#xff0c;字符串混合输入 没有必要什么都学&#xff0c;好用的常用的学一…

基于JavaWeb SSM mybatis 私人健身房系统管理平台设计和实现以及文档报告

基于JavaWeb SSM mybatis 私人健身房系统管理平台设计和实现以及文档报告 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞…

ClamAV:Linux服务器杀毒扫描工具

Clam AntiVirus&#xff08;ClamAV&#xff09;是免费而且开放源代码的防毒软件&#xff0c;软件与病毒码的更新皆由社群免费发布。ClamAV在命令行下运行&#xff0c;它不将杀毒作为主要功能&#xff0c;默认只能查出系统内的病毒&#xff0c;但是无法清除。需要用户自行对病毒…

Linux中查看文件内容的命令

文章目录 一、七类常见的Linux的文件二、显示命令三、分页显示四、显示文件前后内容五、压缩、解压缩六、补充 一、七类常见的Linux的文件 字符文件类型-普通文件&#xff0c;包括纯文本文件、二进制文件、各种压缩文件等。在find命令中&#xff0c;type 选项中用 f来表示d目录…

git学习——tags、release、drop commit

最近一直都在持续学习git相关内容&#xff0c;越来越发现git是一个十分适合大型项目和团队协作进行开发的工具&#xff0c;掌握好了对于我们参与项目维护和开发产品帮助很大&#xff0c;所以要不断持续学习git。 tags & releases tag的创建 当我们在git版本控制中遇到了…

Docker搭建LNMP环境实战(09):安装mariadb

1、编写mariadb部署配置文件 在文件夹&#xff1a;/mnt/hgfs/dockers/test_site/compose下创建文件&#xff1a;test_site_mariadb.yml&#xff0c;内容如下&#xff1a; version: "3.5" services:test_site_mariadb:container_name: test_site_mariadbimage: mari…

【Go】四、包名、访问范围控制、标识符、运算符

文章目录 1、_2、包名3、命名大小影响可访问范围4、运算符5、获取终端输入 1、_ 下划线"_"本身在Go中是一个特殊的标识符&#xff0c;称为空标识符用于忽略某个值 1&#xff09;忽略导入的没使用的包 2&#xff09;忽略某个返回值 2、包名 main包是程序的入口包&a…

【MATLAB第103期】#源码分享 | 基于MATLAB的LIME可解释性线性分类预测模型,2020b以上版本

【MATLAB第103期】#源码分享 | 基于MATLAB的LIME可解释性线性分类预测模型&#xff0c;2020b以上版本 一、模型介绍 LIME&#xff08;Local Interpretable Model-agnostic Explanations&#xff09;是一种用于解释复杂机器学习模型预测结果的算法。它由Marco Ribeiro、Sameer…

设计模式25--策略模式

定义 案例一 案例二 优缺点

AI版青花瓷

3月22日&#xff0c;Suno正式上线V3版本&#xff0c;很多人都称之为AI音乐的"ChatGPT"时刻&#xff0c;从此人人都可以是作曲家&#xff0c;先来听下最近霸榜的只因你太美baby来感受下它的厉害之处&#xff08;我已经被洗脑了哈哈&#xff09; 1. Suno 介绍 根据Sun…

每日学习笔记:C++ STL算法分类

非更易型 更易型 移除型 变序型 排序型 已排序区间算法 数值型算法

Elasticsearch的倒排索引是什么?

文章目录 什么是ES&#xff1f;什么是倒排索引&#xff1f;为什么叫做倒排索引&#xff1f;分词器的使用 什么是ES&#xff1f; Elasticsearch是基于 Apache Lucene【lusen】的搜索引擎&#xff0c;支持Restful API风格【可以使用常见的HTTP请求来访问】&#xff0c;并且搜索速…

抖店如何上架商品?这些细节要注意!否则罚款了别怪我没提醒你!

哈喽~我是电商月月 有朋友私信我一个问题&#xff0c;说是他上架商品后&#xff0c;被判类目错放了 情节严重扣了全部的2000块保证金 申述后没通过&#xff0c;还能要回来吗&#xff1f; 其实这种情况你确实是有错放的现象&#xff0c;误判的可能性很小&#xff0c;所以申述…

metasploit使用及内网笔记

1 基本操作 Metasploit就是一个漏洞框架。它的全称叫做The Metasploit Framework&#xff0c;简称叫做MSF。Metasploit作为全球最受欢迎的工具&#xff0c;不仅仅是因为它的方便性和强大性&#xff0c;更重要的是它的框架。它允许使用者开发自己的漏洞脚本&#xff0c;从而进行…

进销存管理系统:食品批发零售迈向数字化未来-亿发

随着消费逐步复苏&#xff0c;食品批发零售行业也迎来了客流的回升&#xff0c;实体店重新焕发了生机。然而&#xff0c;随着数字化时代的来临&#xff0c;传统的食品批发零售企业面临着新的挑战和机遇。些企业正积极实施数字化转型&#xff0c;通过布局线上线下多业态的融合发…

Linux系统使用Docker部署MeterSphere并实现公网访问本地测试平台

文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…