代码随想录算法训练营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;}
};

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

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

相关文章

小蓝本--因式分解(习题1)讲解

这几天要备战期中&#xff0c;下一期可能要等暑假了...... 小升初的压力真是紧扣于头啊&#xff0c;为了分到一个好班&#xff0c;拼了&#xff01; 对了&#xff0c;下一期可能在寒假更&#xff0c;见谅&#xff01; 1分解因式&#xff1a; 公因式&#xff1a; 答案&#xff…

vue3--element-plus-抽屉文件上传和富文本编辑器

一、封装组件 article/components/ArticleEdit.vue <script setup> import { ref } from vue const visibleDrawer ref(false)const open (row) > {visibleDrawer.value trueconsole.log(row) }defineExpose({open }) </script><template><!-- 抽…

iptables---防火墙

防火墙介绍 防火墙的作用可以理解为是一堵墙&#xff0c;是一个门&#xff0c;用于保护服务器安全的。 防火墙可以保护服务器的安全&#xff0c;还可以定义各种流量匹配的规则。 防火墙的作用 防火墙具有对服务器很好的保护作用&#xff0c;入侵者必须穿透防火墙的安全防护…

排序算法--快速排序

前提&#xff1a; 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小&#xff0c;然后再按此方法对这两部分…

【Leetcode每日一题】 综合练习 - 全排列 II(难度⭐⭐)(71)

1. 题目解析 题目链接&#xff1a;47. 全排列 II 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 算法思路梳理 为了生成给定数组nums的全排列&#xff0c;同时避免由于重复元素导致的重复排列&#xff0c;我们可以遵…

快速上手RabbitMQ

安装RabbitMQ 首先将镜像包上传到虚拟机&#xff0c;使用命令加载镜像 docker load -i mq.tar 运行MQ容器 docker run \-e RABBITMQ_DEFAULT_USERitcast \-e RABBITMQ_DEFAULT_PASS123321 \-v mq-plugins:/plugins \--name mq \--hostname mq \-p 15672:15672 \-p 5672:5672 …

如何使用 GPT API 从 PDF 出版物导出研究图表?

原文地址&#xff1a;how-to-use-gpt-api-to-export-a-research-graph-from-pdf-publications 揭示内部结构——提取研究实体和关系 2024 年 2 月 6 日 介绍 研究图是研究对象的结构化表示&#xff0c;它捕获有关实体的信息以及研究人员、组织、出版物、资助和研究数据之间的关…

brpc profiler

cpu profiler cpu profiler | bRPC MacOS的额外配置 在MacOS下&#xff0c;gperftools中的perl pprof脚本无法将函数地址转变成函数名&#xff0c;解决办法是&#xff1a; 安装standalone pprof&#xff0c;并把下载的pprof二进制文件路径写入环境变量GOOGLE_PPROF_BINARY_PA…

Microsoft 365 for Mac(Office 365)v16.84正式激活版

office 365 for mac包括Word、Excel、PowerPoint、Outlook、OneNote、OneDrive和Teams的更新。Office提供了跨应用程序的功能&#xff0c;帮助用户在更短的时间内创建令人惊叹的内容&#xff0c;您可以在这里创作、沟通、协作并完成重要工作。 Microsoft 365 for Mac(Office 36…

1. 深度学习笔记--神经网络中常见的激活函数

1. 介绍 每个激活函数的输入都是一个数字&#xff0c;然后对其进行某种固定的数学操作。激活函数给神经元引入了非线性因素&#xff0c;如果不用激活函数的话&#xff0c;无论神经网络有多少层&#xff0c;输出都是输入的线性组合。激活函数的意义在于它能够引入非线性特性&am…

【webrtc】MessageHandler 7: 基于线程的消息处理:切换main线程向observer发出通知

以当前线程作为main线程 RemoteAudioSource 作为一个handler 仅实现一个退出清理的功能 首先on message的处理会切换到main 线程 :main_thread_其次,这里在main 线程对sink_ 做清理再次,在main 线程做出状态改变,并能通知给所有的observer 做出on changed 行为。对接mediac…

clang:在 Win10 上编译 MIDI 音乐程序(二)

先从 Microsoft C Build Tools - Visual Studio 下载 1.73GB 安装 "Microsoft C Build Tools“ 访问 Swift.org - Download Swift 找到 Windows 10&#xff1a;x86_64 下载 swift-5.10-RELEASE-windows10.exe 大约490MB 建议安装在 D:\Swift\ &#xff0c;安装后大约占…

《金融研究》:普惠金融改革试验区DID工具变量数据(2012-2023年)

数据简介&#xff1a;本数据集包括普惠金融改革试验区和普惠金融服务乡村振兴改革试验区两类。 其中&#xff0c;河南兰考、浙江宁波、福建龙岩和宁德、江西赣州和吉安、陕西铜川五省七地为普惠金融改革试验区。山东临沂、浙江丽水、四川成都三地设立的是普惠金融服务乡村振兴…

手撸Mybatis(二)—— 配置项的获取

本专栏的源码&#xff1a;https://gitee.com/dhi-chen-xiaoyang/yang-mybatis。 配置项解析 在mybatis中&#xff0c;一般我们会定义一个mapper-config.xml文件&#xff0c;来配置数据库连接的相关信息&#xff0c;以及我们的mapperxml文件存放目录。在本章&#xff0c;我们会…

docker-compose启动mysql5.7报错

描述一下问题经过&#xff1a; 使用docker compose 部署mysql5.7 文件如下: 使用命名卷的情况下&#xff0c;匿名卷不存在该问题 services:mysql:restart: alwaysimage: mysql:5.7container_name: mysql-devports:- 3306:3306environment:- MYSQL_DATABASEdev- MYSQL_ROOT_PAS…

团队经理口才训练教案(3篇)

团队经理口才训练教案&#xff08;3篇&#xff09; **篇&#xff1a;基础口才训练 一、教学目标 让团队经理了解口才在团队管理中的重要性。 教授基础口才技巧&#xff0c;如发音、语速、语调等。 二、教学内容 口才的重要性 强调团队经理的口才能力对团队凝聚力、沟通…

详细介绍ARM-ORACLE Database 19c数据库下载

目录 1. 前言 2. 获取方式 2.1 ORACLE专栏 2.2 ORACLE下载站点 1. 前言 现有网络上已有非常多关于ORACLE数据库机下载的介绍&#xff0c;但对于ARM平台的介绍不多&#xff0c;借此机会我将该版的下载步骤做如下说明&#xff0c;希望能够一些不明之人提供帮助和参考 2. 获…

分享一篇关于AGI的短文:苦涩的教训

学习强化学习之父、加拿大计算机科学家理查德萨顿&#xff08; Richard S. Sutton &#xff09;2019年的经典文章《The Bitter Lesson&#xff08;苦涩的教训&#xff09;》。 文章指出&#xff0c;过去70年来AI研究走过的最大弯路&#xff0c;就是过于重视人类既有经验和知识&…

Flutter笔记:美工设计.导出视频到RIVE

Flutter笔记 美工设计.导出视频到RIVE - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28…

目标跟踪—卡尔曼滤波

目标跟踪—卡尔曼滤波 卡尔曼滤波引入 滤波是将信号中特定波段频率滤除的操作&#xff0c;是抑制和防止干扰的一项重要措施。是根据观察某一随机过程的结果&#xff0c;对另一与之有关的随机过程进行估计的概率理论与方法。 历史上最早考虑的是维纳滤波&#xff0c;后来R.E.卡…