算法学习打卡day40|343. 整数拆分、96.不同的二叉搜索树

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。

思路:

  • 思路就是把整数拆分成两数之和,三数以上可以不用管,因为三数以上其实就是两数拆分的,我们就用两个数来做题,分别取第一个数和第一个数的dp之间的最大值,以及第二个数和第二个数dp之间的最值,然后相乘就是当前组的最大值,最后不断循环和dp[i]比较取最值即可。
  • 动态规划五部曲:
    1. 分析dp数组含义:dp[ i ]数组代表下标为i的整数拆分后元素乘积的的最大值
    2. 分析递推公式: dp[i] = max(dp[i], max(dp[i - j], i - j) * max(dp[j], j));
    3. dp数组初始化:因为我们拆分是从1开始拆分的那么下标0可以不用管,把下标1赋值为1,2也赋值为1,因为2只能拆分为1+1.
    4. 遍历顺序:显然是从前往后遍历,我们遍历的时候从下标i = 3开始,内层循环是去拆分i,比如3从1开始拆分为1和2,但是这里上界其实到 i / 2就可以了,多了就重复了。
    5. 推导数组结果:在这里插入图片描述

代码实现:

int integerBreak(int n) {/*dp[n] = max(dp[1]dp[n - 1],dp[2]dp[n - 2]..., dp[n / 2]dp[n - n / 2]);即:dp[i] = max(dp[i], max(dp[i - j], i - j) * max(dp[j], j));*/vector<int>dp(n + 1, 0);dp[1] = 1, dp[2] = 1;int left = 0, right = 0;for (int i = 3; i <= n; ++i) {for (int j = 1; j <= i / 2; ++j) {left = max(j, dp[j]);right = max(i - j, dp[i - j]);dp[i] = max(left * right, dp[i]);}}return dp[n];}
  • 这里left取最值那一步是可以省略的,为什么?
    • 因为代码实现方法是对j和i- j同时判断是否需要拆分,但是就算 j 它再怎么拆也是拆分成1 - i之间的某个元素再加上另外一个数或一组数(省去left取最值写法其实把这一个数或一组数包到dp[i - j]里了),所以,取到最值的时候,j 一定是1- i之间的某个值,然后dp序列是递增的,那么最值一定不在后 i / 2 里(随着基数增大),所以 j 的上界可以是 i / 2。
    • 数学证明如下(节选自力扣题解的某位同学回答):
      • 因为j * dp[i - j]包含了dp[j] * dp[i - j],这是可以证明的: 对j最优拆分:j = a1 + a2 +…+an; 对i - j 最优拆分:i - j = b1 + b2 +…+bn; 所以有 dp[j] = a1 * a2 … an; dp[i - j] = b1 * b2 *… bn; dp[i] * dp[i - j] = (a1 *a2 *…an) * (b1 * b2 … bn) = a1 * (a2 * … * an * b1 * b2 … bn) 令 k = a1,必有i - k = a2 + … + an + b1 + b2 +…+ bn(这就是对 i - k 的一种拆分) 也就是说如果以上这种对i - k的一种拆分是最优的,那么必有dp[j] * dp[i - j] = k * dp[i - k] 所以此时j * dp[i - j]包含dp[j] * dp[i - j]; 如果以上这种对i - k的拆分不是最优的,那这种拆分方案虽不会被j * dp[i - j]包含但也不会是答案;

96.不同的二叉搜索树

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

示例 1:
在这里插入图片描述
输入:n = 3
输出:5

思路:

  • 我的思路是这样的,1到n的每个数字都可以作为根节点,那么外层for循环还是老套度去求dp数组,内层for循环去决定哪个数子作为根节点,然后将左右节点的dp值乘起来,然后不断加到dp[i]上。
  • 动态规划五部曲:
    1. 分析dp数组含义:dp[ i ]数组代表下标为i的整数的二叉树种类
    2. 分析递推公式: dp[n] = dp[n - 1] * dp[0] + dp[n - 2] * dp[1] + ... + dp[1]*dp[n - 2] + dp[0]* dp[n - 1]
    3. dp数组初始化:因为我们左子树可以是0个节点,而且我们要做乘法,所以下标0赋值为1,把下标1也赋值为1,遍历的时候下标从2开始
    4. 遍历顺序:显然是从前往后遍历,我们遍历的时候从下标 i = 2开始,那么外层for循环还是老套度去求dp数组,内层for循环去决定哪个数子作为根节点,然后将左右子树节点数的dp值乘起来,然后不断加到dp[i]上。
    5. 推导数组结果:1 1 2 5 14…

代码实现

int numTrees(int n) {if (n < 2) return 1;//dp[n] = dp[n - 1] * dp[0] + dp[n - 2] * dp[1] + ... + dp[1]*dp[n - 2] + dp[0]* dp[n - 1]vector<int> dp(n + 1);dp[0] = 1, dp[1] = 1;for (int i = 2; i <= n; ++i) {for (int j = 1; j <= i; ++j) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}

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

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

相关文章

一条 SQL 是如何在 MyBatis 中执行的

前言 MyBatis 执行 SQL 的核心接口为 SqlSession 接口&#xff0c;该接口提供了一些 CURD 及控制事务的方法&#xff0c;另外还可以通过 SqlSession 先获取 Mapper 接口的实例&#xff0c;然后通过 Mapper 接口执行 SQL&#xff0c;Mapper 接口方法的执行最终还是委托到 SqlSe…

Unity屏幕中涂鸦

LineRenderer LineRenderer是Unity中的一个组件&#xff0c;用于在场景中绘制简单的线段。 LineRenderer组件允许你通过设置一系列顶点来定义线段的形状和外观。它会根据这些顶点自动在场景中绘制出线段。 下面是LineRenderer的一些重要属性和方法&#xff1a; positionCou…

栈及其栈的模拟实现和使用

1. 栈(Stack) 1.1 概念 栈 &#xff1a;一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO &#xff08; Last In First Out &#xff09;的原则…

初识FFmpeg

前言 无意间见到群里的小伙伴展示视频工具。功能比较多&#xff0c;包括视频编码修改&#xff0c;画质处理&#xff0c;比例处理、名称提取&#xff0c;剪辑、标题拆解。因此开始了FFmpeg学习。以下摘自百度百科的解释。 FFmpeg是一套可以用来记录、转换数字音频、视频&#xf…

【Proteus仿真】【Arduino单片机】简易电子琴

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用无源蜂鸣器、按键等。 主要功能&#xff1a; 系统运行后&#xff0c;按下K1-K7键发出不同音调。 二、软件设计 /* 作者&#xff1a;嗨小易&a…

视频平台跨网级联视频压缩解决方案

一、 简介 视频监控领域对带宽有着较大的需求&#xff0c;这是因为视频流需要实时占用网络带宽资源。视频监控的传输带宽是组网结构的基础保障&#xff0c;关系到视频监控的稳定性、可靠性和可拓展性等因素。例如&#xff0c;720P的视频格式每路摄像头的比特率为2Mbps&#xff…

【机器学习合集】模型设计之网络宽度和深度设计 ->(个人学习记录笔记)

文章目录 网络宽度和深度设计1. 什么是网络深度1.1 为什么需要更深的模型浅层学习的缺陷深度网络更好拟合特征学习更加简单 2. 基于深度的模型设计2.1 AlexNet2.2 AlexNet工程技巧2.3 VGGNet 3. 什么是网络宽度3.1 为什么需要足够的宽度 4. 基于宽度模型的设计4.1 经典模型的宽…

在IDEA运行spark程序(搭建Spark开发环境)

建议大家写在Linux上搭建好Hadoop的完全分布式集群环境和Spark集群环境&#xff0c;以下在IDEA中搭建的环境仅仅是在window系统上进行spark程序的开发学习&#xff0c;在window系统上可以不用安装hadoop和spark&#xff0c;spark程序可以通过pom.xml的文件配置&#xff0c;添加…

【洛谷算法题】P5710-数的性质【入门2分支结构】

&#x1f468;‍&#x1f4bb;博客主页&#xff1a;花无缺 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P5710-数的性质【入门2分支结构】&#x1f30f;题目描述&#x1f30f;输入格式&a…

开源库存管理系统InvenTree的安装

本文是应网友 shijie880500 要求折腾的&#xff1b; 什么是 InvenTree &#xff1f; InvenTree 是一个开源的库存管理系统&#xff0c;提供强大的低级别库存控制和零件跟踪。InvenTree 系统的核心是 Python/Django 数据库后端&#xff0c;它提供了一个管理界面&#xff08;基于…

绝缘检测原理和绝缘电阻计算方法

文章目录 简介绝缘检测功能绝缘检测原理绝缘电阻检测的常用方法不平衡电桥法 绝缘电阻绝缘电阻的计算 绝缘检测开启或关闭为什么根据 V1 &#xff1c; V2 或 V1 ≥ V2 判断是上桥臂并入电阻还是下桥臂并入电阻 简介 绝缘检测是判断动力&#xff08;正、负&#xff09;总线与外…

Flutter三棵树的创建流程

一、Flutter常见的家族成员 Widget常见的家族成员 Element常见的家族成员 Render常见的家族成员 二、示例代码对应的Flutter Inspector树 示例代码&#xff1a;MyApp->MyHomePage->ErrorWidget&#xff0c;包含了StatelessWidget、StatefulWidget、LeafRenderObjectWid…

位运算与简单应用

一.位运算的基本概念&#xff1a; 首先&#xff0c;位运算是针对二进制的&#xff0c;(数字本来int,4字节,下面假设为1字节)。比如数字12&#xff0c;它的二进制本来是&#xff1a; 0000 0000 0000 0000 0000 0000 0000 1100 因为前面的数字大都是0&#xff0c;所以为了简写…

火影忍者游戏攻略大公开!成为忍者大师的秘诀揭秘

大家好&#xff01;作为火影忍者游戏的玩家&#xff0c;我们都希望能够在游戏中成为优秀的忍者大师&#xff0c;战胜强大的对手。为了帮助大家实现这一目标&#xff0c;我想分享一些实用的攻略和技巧。 首先&#xff0c;熟悉忍者技能是成为忍者大师的基础。在火影忍者游戏中&am…

C语言_自定义类型详解

文章目录 前言一.结构体的声明1.1结构体的基础知识1.2结构的声明1.3特殊声明1.4结构体的自引用在结构中包含一个类型为该结构本身的成员是否可以&#xff1f;正确的自引用方式匿名结构体类型和typedef的结合形式 1.5 结构体变量的定义和初始化结构体定义与初始化结构体里嵌套结…

【Linux进程】再谈软件—操作系统(Operator System)

目录 操作系统(Operator System) 概念 设计OS的目的 如何理解 "管理"——先描述再组织 系统调用和库函数概念 总结 操作系统(Operator System) 概念 任何计算机系统都包含一个基本的程序集合&#xff0c;称为操作系统(OS)。 笼统的理解&#xff0c;操作系统…

【python】路径管理+路径拼接问题

路径管理 问题相对路径问题绝对路径问题 解决os库pathlib库最终解决 问题 环境&#xff1a;python3.7.16 win10 相对路径问题 因为python的执行特殊性&#xff0c;使用相对路径时&#xff0c;在不同路径下用python指令会有不同的索引效果&#xff08;python的项目根目录根据执…

利用Graviton2和S3免费套餐搭建私人网盘

网盘是一种在线存储服务&#xff0c;提供文件存储&#xff0c;访问&#xff0c;备份&#xff0c;贡献等功能&#xff0c;是我们日常中不可或缺的一种服务。很多互联网公司都为个人和企业提供免费的网盘服务。但这些免费服务都有一些限制&#xff0c;比如限制下载速度&#xff0…

下载树莓派对应的64位Ubuntu系统步骤

说点废话&#xff1a;因为ros2需要安装在64位Ubuntu上面&#xff0c;所以安装64位最合适&#xff1b; 第一步打开https://cn.ubuntu.com/ 网站&#xff1b;选择下载--->iot----> 选择这个镜像文件下载。我觉得镜像文件是img格式的&#xff0c;跟iso文件区别是&#xff…