代码随想录算法训练营第四十一天 | 343.整数拆分、66.不同的二叉搜索树

本文主要是介绍代码随想录算法训练营第四十一天 | 343.整数拆分、66.不同的二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

343.整数拆分

题目链接:343.整数拆分

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

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

文章讲解/视频讲解:https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html

思路

首先设置dp数组,dp数组中的每一位代表着当前下标所代表的整数,可以得到的乘积最大值。

初始化时,dp[0] = 0, dp[1] = 1;其余下标均初始化为零。

动态规划的递推公式:

int value1 = max(j, dp[j]), value2 = max(i - j, dp[i - j]);
dp[i] = max(dp[i], value1 * value2); 

其中j的范围为[0, i/2]。

注意,因为这里dp下标的每一个值为k个正整数乘积的最大值,而k大于等于2,因此存在一种可能,j > dp[j],比如当j = 3时,dp[j] = 2。

C++实现

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 = 0;j<=i / 2;j++){int value1 = max(j, dp[j]), value2 = max(i - j, dp[i - j]);dp[i] = max(dp[i], value1 * value2);}}return dp[n];}
};

66.不同的二叉搜索树

题目链接:66.不同的二叉搜索树

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

文章讲解/视频讲解:https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

思路

这道题的递推式挺不好想的。

首先确定一下dp数组以及下标的含义。dp[i]为i个不同元素节点组成的二叉搜索树的个数。

递推公式:dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量],所以递推公式为:dp[i] += dp[j - 1] * dp[i - j],j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量。

初始化时,dp[0] = 1。在遍历时,采用两层循环,外层循环遍历i,即代表当前二叉搜索树的个数,内存循环遍历j。

C++实现

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

这篇关于代码随想录算法训练营第四十一天 | 343.整数拆分、66.不同的二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/634503

相关文章

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)