当前位置: 首页 > news >正文

力扣 343. 整数拆分

题目来源:https://leetcode.cn/problems/integer-break/description/

 

C++题解1:动态规划。dp[i] 代表数字i拆分后得到的最大乘积。递归公式为拆分后两个数的最大乘积相乘,即 dp[i] = max(dp[i], dp[j] * dp[i-j])。对于n=2或3需要另外讨论。

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

C++题解2(来源代码随想录):动规五部曲。

  1. 确定dp数组(dp table)以及下标的含义。dp[i]:分拆数字i,可以得到的最大乘积为dp[i]。
  2. 确定递推公式。 dp[i]最大乘积是怎么得到的呢?其实可以从1遍历j,然后有两种渠道得到dp[i]。一个是j * (i - j) 直接相乘;另一个是j * dp[i - j],相当于是拆分(i - j),对这个拆分不理解的话,可以回想dp数组的定义。那有同学问了,j怎么就不拆分呢?j是从1开始遍历,拆分j的情况,在遍历j的过程中其实都计算过了。那么从1遍历j,比较(i - j) * j和dp[i - j] * j 取最大的。递推公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));也可以这么理解,j * (i - j) 是单纯的把整数拆分为两个数相乘,而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
  3. dp的初始化。初始化dp[2] = 1。
  4. 确定遍历顺序。先来看看递归公式:dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))。dp[i] 是依靠 dp[i - j]的状态,所以遍历i一定是从前向后遍历,先有dp[i - j]再有dp[i]。
  5. 举例推导dp数组
class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);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];}
};

C++题解3(来源代码随想录):贪心算法。“拆分一个数n 使之乘积最大,那么一定是拆分成m个近似相同的子数相乘才是最大的”。每次拆成n个3,如果剩下是4,则保留4,然后相乘,但是这个结论需要数学证明其合理性!

class Solution {
public:int integerBreak(int n) {if (n == 2) return 1;if (n == 3) return 2;if (n == 4) return 4;int result = 1;while (n > 4) {result *= 3;n -= 3;}result *= n;return result;}
};

相关文章:

力扣 343. 整数拆分

题目来源&#xff1a;https://leetcode.cn/problems/integer-break/description/ C题解1&#xff1a;动态规划。dp[i] 代表数字i拆分后得到的最大乘积。递归公式为拆分后两个数的最大乘积相乘&#xff0c;即 dp[i] max(dp[i], dp[j] * dp[i-j])。对于n2或3需要另外讨论。 cla…...

【JavaWeb】正则表达式

&#x1f384;欢迎来到边境矢梦的csdn博文&#xff0c;本文主要讲解Java 中正则表达式 的相关知识&#x1f384; &#x1f308;我是边境矢梦&#xff0c;一个正在为秋招和算法竞赛做准备的学生&#x1f308; &#x1f386;喜欢的朋友可以关注一下&#x1faf0;&#x1faf0;&am…...

Vue中常用到的标签和指令

一、标签 在 Vue 中&#xff0c;并没有特定的标签是属于 Vue 的&#xff0c;因为 Vue 是一个用于构建用户界面的框架&#xff0c;可以与 HTML 标签一起使用。Vue 中可以使用的标签和元素基本上与 HTML 标准一致。 以下是一些常见的HTML标签&#xff0c;也可以在 Vue 中使用&a…...

C++设计模式之访问者模式

C访问者设计模式 文章目录 C访问者设计模式什么是设计模式什么是访问者设计模式该模式有什么优缺点优点缺点 如何使用 什么是设计模式 设计模式是一种通用的解决方案&#xff0c;用于解决特定的一类问题。它是一种经过验证的代码组织方式&#xff0c;可以帮助开发人员更快地实…...

Java8的stream常用的操作

记录一下常用的用法 定义测试对象 Datapublic class Employee {//idprivate Integer id;//姓名private String name;//年龄private Integer age;//身高private Double height;//存款private BigDecimal deposit;public Employee(Integer id, String name, Integer age, Double…...

传统计算机视觉

传统计算机视觉 计算机视觉难点图像分割基于主动轮廓的图像分割基于水平集的图像分割交互式图像分割基于模型的运动分割 目标跟踪基于光流的点目标跟踪基于均值漂移的块目标跟踪基于粒子滤波的目标跟踪基于核相关滤波的目标跟踪 目标检测一般目标检测识别之特征一般目标检测识别…...

13-3_Qt 5.9 C++开发指南_基于QReadWriteLock 的线程同步

使用互斥量时存在一个问题: 每次只能有一个线程获得互斥量的权限。如果在一个程序中有多个线程读取某个变量&#xff0c;使用互斥量时也必须排队。而实际上若只是读取一个变量&#xff0c;是可以让多个线程同时访问的&#xff0c;这样互斥量就会降低程序的性能。 例如&#xf…...

opencv04-掩膜

opencv04-掩膜 抠图 #include <iostream> #include <opencv2/highgui/highgui.hpp> #include <opencv2/opencv.hpp> #include <vector> #include <array> #include <algorithm>using namespace std; using namespace cv;int main() {str…...

python解析帆软cpt及frm文件(xml)获取源数据表及下游依赖表

#!/user/bin/evn python import os,re,openpyxl 输入&#xff1a;帆软脚本文件路径输出&#xff1a;帆软文件检查结果Excel#获取来源表 def table_scan(sql_str):# remove the /* */ commentsq re.sub(r"/\*[^*]*\*(?:[^*/][^*]*\*)*/", "", sql_str)# r…...

TypeScript

TypeScript 简称&#xff1a; TS &#xff0c;是 JavaScript 的超集 &#xff0c;简单来说就是&#xff1a; JS 有的 TS 都有 TypeScript Type JavaScript &#xff08;在 JS 基础之上&#xff0c; 为 JS 添加了类型支持 &#xff09; TypeScript 是 微软 开发…...

解决启动vue前端报错:npm ERR! Missing script: “serve“

目录 一、遇到问题 二、出现报错的两个原因 三、解决办法 一、遇到问题 npm ERR! Missing script: "serve" npm ERR! npm ERR! To see a list of scripts, run: npm ERR! npm run npm ERR! A complet...

数据结构 | 线性数据结构——列表

目录 一、无序列表抽象数据类型 二、实现无序列表&#xff1a;链表 2.1 Node类 2.2 UnorderedList类 三、有序列表抽象数据类型 四、实现有序列表 列表是元素的集合&#xff0c;其中每一个元素都有一个相对于其他元素的位置。更具体地说&#xff0c;这种列表成为无序列表…...

【ARM 常见汇编指令学习 6 - bic(位清除), orr(位或), eor(异或)】

文章目录 BIC 指令ORR 位或指令EOR 异或指令 上篇文章&#xff1a;ARM 常见汇编指令学习 5 – arm64汇编指令 wzr 和 xzr 下篇文章&#xff1a;ARM 常见汇编指令学习 7 - LDR 指令与LDR伪指令及 mov指令 BIC 指令 指令格式 bic{条件}{S} Rd&#xff0c;Rn&#xff0c;operan…...

在CSDN学Golang场景化解决方案(EFK分布式日志系统方案)

一&#xff0c;ElasticSearch 分布式集群部署 在 Golang EFK 分布式日志系统方案中&#xff0c;ElasticSearch 是一个分布式搜索引擎和数据存储库&#xff0c;它可以用于存储和搜索大量的日志数据。以下是 ElasticSearch 分布式集群部署的步骤&#xff1a; 下载 ElasticSearc…...

MySQL篇

文章目录 一、MySQL-优化1、在MySQL中&#xff0c;如何定位慢查询?2、SQL语句执行很慢, 如何分析呢&#xff1f;3、了解过索引吗&#xff1f;&#xff08;什么是索引&#xff09;4、索引的底层数据结构了解过嘛 ?5、什么是聚簇索引什么是非聚簇索引 ?6、知道什么是回表查询嘛…...

图数据库Neo4j学习四——Spring Data NEO

1配置 1.1Maven依赖 <!--neo4j --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-neo4j</artifactId> </dependency>1.2yml配置 spring:data:neo4j:uri: bolt://localhost:76…...

UE虚幻引擎 UTextBlock UMG文本控件超过边界区域以后显示省略号

版本 5.2.1 裁剪 - 剪切 - 剪切到边界 裁剪 - 高级 - 溢出策略 - 省略...

Spring Boot实践五 --异步任务线程池

一、使用Async实现异步调用 在Spring Boot中&#xff0c;我们只需要通过使用Async注解就能简单的将原来的同步函数变为异步函数&#xff0c;Task类实现如下&#xff1a; package com.example.demospringboot;import lombok.extern.slf4j.Slf4j; import org.springframework.s…...

<C语言> 动态内存管理

1.动态内存函数 为什么存在动态内存分配&#xff1f; int main(){int num 10; //向栈空间申请4个字节int arr[10]; //向栈空间申请了40个字节return 0; }上述的开辟空间的方式有两个特点&#xff1a; 空间开辟大小是固定的。数组在声明的时候&#xff0c;必须指定数组的…...

【ASPICE】:学习记录

学习记录 ASPICE中文资料什么是ASPICE过程参考模型 ASPICE全称“Automotive Software Process Improvement and Capability dEtermination”&#xff0c;即“汽车软件过程改进及能力评定”模型框架 ASPICE中文资料 主要资料来源 什么是ASPICE 过程参考模型...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...