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

343. 整数拆分

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。

提示:

  • 2 <= n <= 58

思路:(动态规划)

法一:

对于正整数 n,当 n ≥ 2 时,可以拆分成至少两个正整数的和。令 x 是拆分出的第一个正整数,则剩下的部分是 n − x,n − x 可以不继续拆分,或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积,因此可以使用动态规划求解。

创建数组 dp,其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后,这些正整数的最大乘积。特别地,0 不是正整数,1 是最小的正整数,0 和 1 都不能拆分,因此 dp[0] = dp[1] = 0。

当 i ≥ 2 时,假设对正整数 i 拆分出的第一个正整数是 j(1 ≤ j < i),则有以下两种方案:

  • 将 i 拆分成 j 和 i − j 的和,且 i − j 不再拆分成多个正整数,此时的乘积是 j × (i − j);
  • 将 i 拆分成 j 和 i − j 的和,且 i − j 继续拆分成多个正整数,此时的乘积是 j × dp[i − j]。

因此,当 j 固定时,有 dp[i] = max⁡(j × (i − j), j × dp[i − j])。由于 j 的取值范围是 1 到 i − 1,需要遍历所有的 jjj 得到 dp[i] 的最大值,因此可以得到状态转移方程如下:

dp[i]=max⁡1≤j<i{max⁡(j×(i−j),j×dp[i−j])}d p[i]=\max _{1 \leq j<i}\{\max (j \times(i-j), j \times d p[i-j])\} dp[i]=1j<imax{max(j×(ij),j×dp[ij])}

最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后,这些正整数的最大乘积。

法二:

由于分解成正整数的乘积最大,若分解的正整数有1,不会使乘积变大,所以分解的正整数大于等于2;

  • 又至少分解2个正整数,当 n = 2,或 n = 3 时,最大的乘积分别为1和2;
  • n > 4 时,分解的最小整数为2,否则只会变小;

举一些栗子:

4 = 2 + 2 , 2 * 2 = 4
5 = 2 + 3,  2 * 3 = 6
6 = 3 + 3 , 3 * 3 = 9
7 = 2 + 2 + 3 = 2 + 5 
8 = 2 + 3 + 3 = 2 + 6
9 = 4 + 2 + 3 = 2 + 7
10 = 3 + 3 + 4 = 3 + 7
  • 创建数组 dp,其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后,这些正整数的最大乘积。
  • 由以上可知分解的都可表示为 2 或 3 与另一个数 j,最大乘积就是2 或 3 乘以另一个数的最大乘积dp[j].

代码:(Java)

法一:

public class IntegerBreak {public static void main(String[] args) {// TODO Auto-generated method stubint n = 10;System.out.println(integerBreak(n));}int[] dp = new int[n + 1];dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i - 1; j++) {dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));}}return dp[n];
}

法二:

public class IntegerBreak {public static void main(String[] args) {// TODO Auto-generated method stubint n = 10;System.out.println(integerBreak(n));}public static int integerBreak(int n) {if(n / 2 < 2) {return n - 1;}int[] dp = new int[n + 1];dp[2] = 2;dp[3] = 3;for(int i = 4; i <= n; i++) {dp[i] = Math.max(2*dp[i-2], 3*dp[i-3]);}return dp[n];}
}

运行结果:

在这里插入图片描述

复杂度分析:

时间复杂度O(n2)O(n^2)O(n2),其中 n 是给定的正整数。对于从 2 到 n 的每一个整数都要计算对应的 dp 值,计算一个整数对应的 dp 值需要 O(n) 的时间复杂度,因此总时间复杂度是 O(n2)。(法二时间复杂度为:O(n))

空间复杂度:O(n),其中 n 是给定的正整数。创建一个数组 dp,其长度为 n+1

注:仅供学习参考!

题目来源:力扣。

相关文章:

343. 整数拆分

343. 整数拆分 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。示例 2: 输入: n 10 输出: 36…...

SCAFFOLD: Stochastic Controlled Averaging for Federated Learning学习

SCAFFOLD: Stochastic Controlled Averaging for Federated Learning学习背景贡献论文思想算法局部更新方式全局更新方式实验总结背景 传统的联邦学习在数据异构(non-iid)的场景中很容易产生“客户漂移”(client-drift )的现象&#xff0c;这会导致系统的收敛不稳定或者缓慢。…...

第十四届蓝桥杯三月真题刷题训练——第 3 天

目录 题目1&#xff1a;门牌制作 题目描述 运行限制 代码&#xff1a; 题目2&#xff1a;货物摆放_long 题目描述 答案提交 运行限制 代码&#xff1a; 题目3&#xff1a;跳跃_dp 题目描述 输入描述 输出描述 输入输出样例 运行限制 代码&#xff1a; 题目4&a…...

变量的四大存储类型static extern auto register

变量的四大存储类型static extern auto register外部变量&#xff08;全局变量&#xff09;extern----全局静态存储区定义 引用性声明❗易错点&#xff1a;函数之外未定义的变量一般是外部变量 extern全局变量 与 局部变量的区别‼️ 谨记&#xff1a;声明可以多次&#xff0c;…...

JavaScript基础五、语句

零、文章目录 文章地址 个人博客-CSDN地址&#xff1a;https://blog.csdn.net/liyou123456789个人博客-GiteePages&#xff1a;https://bluecusliyou.gitee.io/techlearn 代码仓库地址 Gitee&#xff1a;https://gitee.com/bluecusliyou/TechLearnGithub&#xff1a;https:…...

青龙面板399乐园

1.拉库 ql raw https://wjkjy.cn/wp-content/uploads/2023/03/1678104978-afaecb98a9df61e.js 2.抓包 7.26 399乐园 每天 七八毛左右 脚本已完成全部任务&#xff0c;自动提现 下载链接&#xff1a;https://3mao.lanzoul.com/izGDh084oogh 抓包链接 https://339.mhhuanyue.c…...

自动化注册组件

// components/index.js export default { install(app) { const req require.context(‘./’, false, /.vue$/) // console.log(req, ‘req’) req.keys().forEach((item) > { // console.log(item, ‘item’) const com req(item).default // console.log(com, ‘com’)…...

【JS代码优化一】分支优化篇

序&#xff1a;如何让代码看起来更优雅&#xff1f;代码是由文字堆叠起来的可以被机器执行的程序。它记载着相关信息&#xff08;状态&#xff09;、表达相关的情绪&#xff08;函数&#xff09;&#xff0c;所以如何能够写出简洁、优雅、健壮、可维护性强的程序至关重要。本系…...

软件测试-接口测试-补充

文章目录 1.持续集成2. mock测试3.Fiddler 抓包工具3.1 弱网测试4. webservice1.持续集成 持续集成概念 重复执行开发提交代码并集成到主干; aim 加速产品迭代 好处 快速发现问题 避免分支大幅度偏离主干 加速产品发布 工具 git:源代码版本工具github:代码仓库jenkins:持续…...

Spring笔记(5):Beans自动装配

为什么需要使用自动装配 在通过XML配置文件进行设置Bean元素注入与声明注册后&#xff0c;我们能够发现一个问题&#xff0c;在项目中是会存在大量对象的&#xff0c;不可能全部都写在XML文件中&#xff0c;那会显得非常的臃肿&#xff0c;不利于后期维护&#xff0c;所以需要用…...

Spark+Vue+Springboot 协同过滤额音乐推荐大数据深度学习项目

一、项目背景 随着互联网的发展,大数据的到来,传统的音乐行业受到了很大的冲击,原有的音乐数字化给人们生活带来了极大的便利。随着数字音乐的兴起,各大音乐平台层出不穷,人们在音乐平台上收听音乐的时,常常因为歌曲信息繁杂,而不能找到自己想听的音乐。为了解决这个问题,音乐…...

JDBC的实现(IDEA版)

前期准备 开发环境&#xff1a; IDEA 2021.1.3 JAVA 1.8 MYSQL 8.0.32 msql用户名:root 密码&#xff1a;123 下载MySQL JDBC 驱动 前往MySQL官网下载对应版本的MySQL Connector/J驱动 &#xff08;下载地址&#xff1a;https://dev.mysql.com/downloads/connector/j/&#xff…...

人员摔倒识别预警系统 人员跌倒检测算法 yolov7

人员摔倒识别预警系统 人员跌倒检测算法基于yolov7网络模型计算机识别技术&#xff0c;人员摔倒识别预警系统 人员跌倒检测算法对画面中人员摔倒进行实时检测识别抓拍告警。YOLOv7 的策略是使用组卷积来扩展计算块的通道和基数。研究者将对计算层的所有计算块应用相同的组参数和…...

Spring-Cloud-Gateway集成Nacos如何做负载均衡?

spring-cloud-alibaba的低版本 如果所用的SpringCloud和Nacos的版本信息如下&#xff1a; <spring-cloud.version>Hoxton.SR10</spring-cloud.version> <spring-cloud-alibaba.version>2.2.6.RELEASE</spring-cloud-alibaba.version>网关的依赖如下&…...

【数据挖掘与商务智能决策】第四章 逻辑回归模型

逻辑回归模型算法原理 逻辑回归模型的数学原理 %matplotlib inline# 补充知识点:Sigmoid函数绘制 import matplotlib.pyplot as plt import numpy as npx = np.linspace(-6, 6) # 通过linspace()函数生成-6到6的等差数列,默认50个数 y = 1.0...

滚动升级回滚

滚动升级回滚 ReplicationController 资源文件 apiVersion: v1 kind: ReplicationController metadata:name: kubia-v1labels:app: kubia spec:replicas: 3template:metadata:name: kubialabels:app: kubiaspec:containers:- image: luksa/kubia:v1name: nodejes --- apiVer…...

2023/3/6 VUE - 组件传值【通信】方式

1 父亲传子代传值【子代使用父代的数据】 1.1 props传值 父亲给儿子传值&#xff1a; 爷爷给孙子传值&#xff1a; 这个props传值的方式&#xff0c;只能一代一代的往下传&#xff0c;不能跨代传值。 有一个问题&#xff1a;子组件不能修改父组件的值&#xff1a; 1.2 …...

MedCalc v20.217 医学ROC曲线统计分析参考软件

MedCalc是一款医学 ROC 曲线统计软件,用于ROC曲线分析的参考软件,医学工作者设计的医学计算器,功能齐全。它可以帮助医生快速作出普通的医学计算,从而对症下药。提供超过76种常用的规则和方法,包括:病人数据、单位参数、费用计算等等。甚至可以将图形另存为BMP,PNG,GIF…...

欢乐消除开心假日协议解密

欢乐消除开心假日协议解密协/议/流/量/解/密分析欢乐消除开心假日这款游戏流量的协议加密方式。序欢乐消除开心假日是一款合成模拟家装的游戏&#xff0c;在这个游戏中&#xff0c;你将成为一位充满热情的设计师&#xff0c;与好友一起经营工作室。你需要根据客户的需求重新设计…...

Android Service知识

一. 概览 Service 是一种可在后台执行长时间运行操作而不提供界面的应用组件。服务可由其他应用组件启动&#xff0c;而且即使用户切换到其他应用&#xff0c;服务仍将在后台继续运行。此外&#xff0c;组件可通过绑定到服务与之进行交互&#xff0c;甚至是执行进程间通信 (IPC…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...