代码随想录算法训练营DAY40\DAY41|C++动态规划Part.3|343.整数拆分、96.不同的二叉搜索树

本文主要是介绍代码随想录算法训练营DAY40\DAY41|C++动态规划Part.3|343.整数拆分、96.不同的二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

DAY40休息日,本篇为DAY41的内容

文章目录

  • 343.整数拆分
    • 思路
      • dp含义
      • 递推公式(难点)
      • 初始化
      • 遍历顺序
      • 打印
    • CPP代码
    • 数学方法
    • 归纳证明法
  • 96.不同的二叉搜索树
    • 思路
      • dp含义
      • 递推公式
      • 初始化
      • 遍历顺序
      • 打印
    • CPP代码
    • 题目总结

343.整数拆分

力扣题目链接

文章讲解:343.整数拆分

视频讲解:动态规划,本题关键在于理解递推公式!| LeetCode:343. 整数拆分

状态:哥们儿把从1-10的整数拆分全写出来了,思路嘎嘎有,要想乘积最大,必须把数字全部拆成2或者3。但是,如何跟动态规划联系起来呢?

看完题解出来了,哥们儿那个属于是数学方法,但是差很多完整的思考,后文会给予证明。

我认为本题更适合使用数学方法来解决,也就是数学归纳法

看到这个题目,会疑问应该拆成两个还是三个还是四个呢?

之前我们说过,动态规划用来解包含重叠子问题的某问题,那么这里直接试试动态规划。

思路

在之前你走过拆分2-10的流程吗,找到什么感觉了吗?当我们在拆10的时候,可能把10拆成4、6(或者是其他的什么),我们之前也拆过4和6,自然拆成2、2、3、3。发现了吗,我们拆10这个问题包含了重叠子问题(拆4和6),所以试试动态规划吧!

dp含义

自然一点的想法:

dp[i]:拆分数字i,可以得到的最大乘积为dp[i]

递推公式(难点)

递推公式的重难点是什么呢?先思考我们如何才能得到dp[i]

首先我们拆分i,肯定首先拆成两个数字,也就是j(i - j)j是遍历1j的所有情况;

如果拆成3个数及3个数以上,我们就是j * dp[i - j],该式子的含义就是把i拆成三个或三个以上数字(因为dp[i - j]包含了所有的拆分方法,且至少拆成两个)

NOTE

为什么公式j * dp[i-j]是成分成2个以上数字呢?

首先我们要搞明白dp[i - j]的含义,拆分数字i-j,可以得到的最大乘积,他就暗含了将i-j拆分成两个或两个以上数字。

为什么j就不拆分了呢?

由于我们是从1开始一直遍历到j,所以已经暗含了拆分j的情况,因为我们还有旁边的dp[i-j]来给j补蛋呢!

综上所述, d p [ i ] = m a x ( d p [ i ] , m a x ( ( i − j ) ∗ j , d p [ i − j ] ∗ j ) ) dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)) dp[i]=max(dp[i],max((ij)j,dp[ij]j))

为什么这里多了个max(dp[i], ...)呢?因为我们之前说过,我们需要遍历1~j的数,所以为了保留每个i当前最大成绩,与新遍历的j上下文做比较,保持dp[i]的最大值更新或者不更新。

初始化

本题中,我们只初始化dp[2]=1,因为严格来说,dp[0] dp[1]不应该初始化,因为这在我们定义dp数组含义时就确定了这俩是没有意义的数值,题中给定的n也是大于等于2的。

遍历顺序

还记得上面我们说把1遍历到j不,这里我们需要两层遍历,对于dp数组那肯定是从左到右了;关于j应该是从1开始,因为从0开始仍然是没有意义的,难道我们还把一个数拆成0和其他数吗?

for (int i = 3; i <= n; i++) {for (int j = 1; j < i - 1; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}
}
//再优化一下子
for (int i = 3; i <= n ; i++) {for (int j = 1; j <= i / 2; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}
}

打印

CPP代码

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

数学方法

归纳证明法

我在写1-10的最优拆分方案过程中,确实感受到了以下规律,这里是leetcode的官解归纳证明法

  • 第一步:证明最优的拆分方案中不会出现大于 4的整数。

假设出现了大于 4 4 4 的整数 x x x,由于$ 2(x−2)>x 在 在 x>4$时成立,将 x拆分成 2和 x−2可以增大乘积。因此最优的拆分方案中不会出现大于 4 的整数。

  • 第二步:证明最优拆分方案中可以不出现整数4

很明显,出现4的话可以用 2 × 2 2 \times2 2×2代替

此时,可知最优的拆分方案只会出现1、2、3三个数字

  • 第三步:证明 n ≥ 5 n \geq5 n5时,最优的拆分方案不会出现整数1.

n ≥ 5 n \geq5 n5时,如果出现了整数1,那么拆分中剩余的数的和为 n − 1 ≥ 4 n-1 \geq4 n14,对应这至少两个整数1和一个大于等于4的数。我们将其中任意一个整数 x x x加上1,乘积都会增大。

此时,可知当 n ≥ 5 n \geq5 n5时,最优拆分方案只有2和3

  • 第三步:证明当 n ≥ 5 n \geq5 n5时,最优的拆分方案中2的个数不会超过3个

如果出现了超过 3 个 2,那么将它们转换成 2 个 3,可以增大乘积,即 3 × 3 > 2 × 2 × 2 3 \times 3 > 2 \times 2 \times 2 3×3>2×2×2

综上, n ≥ 5 n \geq5 n5的最优拆分方案就唯一了,这是因为当最优的拆分方案中2的个数分别为0,1,2个时,就对应着n除以3的余数分别为0,2,1的情况。

并且 n = 4 n = 4 n=4时的拆分方案也可以放入分类讨论的结果;当 2 ≤ n ≤ 3 2\leq n \leq3 2n3时,只有唯一的拆分方案 1 × ( n − 1 ) 1 \times (n - 1) 1×(n1)

int integerBreak(int n) {int (n <= 3) {return n - 1;}int quotient = n / 3; //商int remainder = n % 3; //余数if (remainder == 0) {	 //能被3整除,全部拆成3return (int)pow(3, quotient);}else if (remainder == 1){	//余1return (int)pow(3, quotient - 1) * 4}else {	//余2return (int)pow(3, quotient) * 2;}
}

96.不同的二叉搜索树

力扣题目链接

文章讲解:96.不同的二叉搜索树

视频讲解:动态规划找到子状态之间的关系很重要!| LeetCode:96.不同的二叉搜索树

状态:这个动态规划我知道!有点明显。dp数组肯定是1维的,含义就是组成的不同BST的个数,关于递推公式我列举了n等于1-4时各能组成多少个BST,在写4时发现了大致的规律,但是没能力抽象成数学公式

思路

直观上,我们肯定是要把n=1、2、3直接拉出来比较的。

n=3时,

  • 当1为头结点,其右子树有两个结点,结点布局与n=2时一致
  • 当2为头结点,其左右子树都只有一个结点,布局和n=1一致
  • 当3位头结点,其左子树有两个节点,和n=2时一致

到这里我们就完全挖掘住了重叠的子问题。

dp[3] = 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]

有1个元素的搜索树数量就是dp[1]

有0个元素的搜索树数量就是dp[0]

综上 d p [ 3 ] = d p [ 2 ] ∗ d p [ 0 ] + d p [ 1 ] ∗ d p [ 1 ] + d p [ 0 ] ∗ d p [ 2 ] dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2] dp[3]=dp[2]dp[0]+dp[1]dp[1]+dp[0]dp[2].。

同理, d p [ 4 ] = d p [ 0 ] ∗ d p [ 3 ] + d p [ 1 ] ∗ d p [ 2 ] + d p [ 2 ] ∗ d p [ 1 ] + d p [ 3 ] ∗ d p [ 0 ] dp[4] = dp[0]*dp[3] + dp[1]*dp[2] + dp[2]*dp[1]+ dp[3]*dp[0] dp[4]=dp[0]dp[3]+dp[1]dp[2]+dp[2]dp[1]+dp[3]dp[0],其中 d p [ 3 ] dp[3] dp[3]可以继续拆分,很显然我们的递推公式应该写成:

d p [ i ] = ∑ j = 1 i d p [ j − 1 ] d p [ i − j ] dp[i] = \sum_{j=1}^{i}dp[j-1]dp[i-j] dp[i]=j=1idp[j1]dp[ij]j-1j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量。很明显需要两个循环,一个大循环i还有一个小循环j

dp含义

dp[i]:表示的是i个不同元素节点组成的二叉搜索树的个数为dp[i]

递推公式

上文分析中,已经给出了基本的递推公式

dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

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

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

初始化

从递推公式也可以看出来,本题其实只要初始化dp[0]就可以了,他是推导的基础。

从定义上来讲,空结点也是一颗二叉树,也是一颗二叉搜索树。

综上:dp[0] = 1

遍历顺序

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

那么遍历i里面每一个数作为头结点的状态,用j来遍历。

for (int i = 1; i <= n; i++){for (int j = 1; j <= i; i++) {dp[i] += dp[j - 1] * dp[i - j];}
}

打印

CPP代码

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);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];}
};
  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( n ) O(n) O(n)

题目总结

本题我们用的是一种近似数学归纳法的推理。

在LeetCode官解中,给出了严格的数学证明,我认为这样的思考过程也是非常需要了解的。

  • LeetCode官解(必须手推一下!也不难!)

  • 卡塔兰数:

    • 卡塔兰数往往解决以下几类问题:
      • 有效的括号组合的数量。
      • 不同的二叉搜索树的数量。
      • 凸多边形划分成三角形的方法数量。
      • 在一个正方形格子图中从一角到另一角的路径数量,这些路径仅向上或向右移动,并且不越过对角线。
    • 递推公式 C 0 = 1 , C n + 1 = 2 ( 2 n + 1 ) n + 2 C n C_0=1, C_{n+1}=\frac{2(2n+1)}{n+2}C_n C0=1,Cn+1=n+22(2n+1)Cn
class Solution {
public:int numTrees(int n) {long long C = 1;for (int i = 0; i < n; ++i) {C = C * 2 * (2 * i + 1) / (i + 2);}return (int)C;}
};

这篇关于代码随想录算法训练营DAY40\DAY41|C++动态规划Part.3|343.整数拆分、96.不同的二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

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

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.