力扣(动态规划)-343整数拆分;96不同的二叉搜索树

2024-08-25 01:04

本文主要是介绍力扣(动态规划)-343整数拆分;96不同的二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 整数拆分

题目:

给定⼀个正整数 n,将其拆分为⾄少两个正整数的和,并使这些整数的乘积最⼤化。 返回你可以获得的最⼤乘积。

示例 1:

输⼊: 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输⼊: 10

输出: 36

解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

  • 2 <= n <= 58

说明: 你可以假设 n 不⼩于 2 且不⼤于 58。

动态规划五部曲:

  • 1使用一个一维(二维)dp数组来保存递归结果:

由于我们要求的是对任意的整数n找到其规定条件下的最大乘积,所以首先想到:

状态转移方程dp[i]表示数字i的最大乘积

  • 2.确定递推公式

要找到dp[i]的最大乘积,可以将dp[i]划分为一个不会再被划分的数j,和一个会被划分m次但是总和为 (i-j)的数.

此时由于j不会再被划分,所以要使dp[i]最大,则 就要对(i-j)进行拆分使得拆分后的几个整数的乘积最大,即dp[i-j]。

所以

dp[i]的最大乘积=j * dp[i-j]

由于j是一个不确定的数,所以需要对j进行遍历,确定j为某个值时使得j*dp[i-j]最大

上面我们就解释了为什么dp[i]=j*dp[i-j],但是有一个容易被忽略的问题:

题目我们的dp[i]是由至少两个整数相乘得到的。那么同样的dp[i-j]也是由至少两个整数组成的。所以这里遗漏了一种情况:若是i-j不进行划分时得到dp[i]的最大值,那么dp[i]=j*(i-j)

综上所诉,我们的递推公式应该是dp[i]=max(   j * dp[i-j],   j*(i-j)  )

  • 3.Dp数组如何初始化

由于题目中最小的能够进行划分的数是2,所以严格的定义来说,我们只需要从2开始初始化递推函数:dp[2]=1;  (1*1=1)

但此时要注意,递推公式dp[i]=j*dp[i-j]中的i-j要保证大于等于2

  • 4.确定遍历序列(eg:不同路径)

从递推公式dp[i]=j*dp[i-j]可以看出后面的结果是由前面i-j推导出来的,所以i⼀定是从小到大遍历,先有dp[i - j]再有dp[i]

  • 5.举例推导递推公式,避免错误
class Solution {
public:int integerBreak(int n) {vector<int>dp(n+1,0);dp[2]=1;for(int i=3;i<=n;i++){//dp[i]中的ifor(int j=1;j<=i-2;j++){//要保证dp[i-j]中的i-j>=2int t=max(j*dp[i-j], j*(i-j));if(t>dp[i])dp[i]=t;}}return dp[n];}
};

96不同的二叉搜索树

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

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 19

对于任意一个节点,它的组成是根节点,左孩子和右孩子。当一共有三个节点时,忽略节点的值,它可能的布局是:(2^0)表示最孩子两个节点,右孩子0个节点,必然有一个节点作为根节点

(2^0),(0^2)(1^1),三种可能存在的节点排序,而对于右两个节点的分支又可以有(0^1)(1^0)两个排序结构,所以有三个节点时可能存在的不同结构有2+1+2=5种

相当于有n个节点就把n进行拆分,一个作为根节点,剩余的n-1个根据结构放在左右子树上,此时就可以将情况划分为左子树有j个节点,则右子树有(n-1-j)个节点,则有递推公式dp[n]=dp[j]*[n-1-j],由于j个个数可以改变,所以j进行遍历,从0~n-1 。

1. 确定dp数组(dp table)以及下标的含义

dp[i] : 1到i为节点组成的⼆叉搜索树的个数为dp[i]。

2. 确定递推公式

在上⾯的分析中,其实已经看出其递推关系, dp[i] += dp[以j为头结点左⼦树节点数量] * dp[以j为头结点右⼦树节

点数量]

j相当于是头结点的元素,从1遍历到i为⽌。

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

3. dp数组如何初始化

初始化,只需要初始化dp[0]就可以了,推导的基础,都是dp[0]。

那么dp[0]应该是多少呢?

从定义上来讲,空节点也是⼀棵⼆叉树,也是⼀棵⼆叉搜索树。

从递归公式上来讲,dp[以j为头结点左⼦树节点数量] * dp[以j为头结点右⼦树节点数量] 中以j为头结点左⼦树节点

数量为0,也需要dp[以j为头结点左⼦树节点数量] = 1, 否则乘法的结果就都变成0了。

所以初始化dp[0] = 1

4. 确定遍历顺序

⾸先⼀定是遍历节点数,从递归公式:dp[i] += dp[j - 1] * dp[i - j]可以看出,节点数为i的状态是依靠 i之前节点数

的状态。

5:举例推导递推公式,避免错误

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

这篇关于力扣(动态规划)-343整数拆分;96不同的二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计