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

LeetCode343. 整数拆分

343. 整数拆分

文章目录

    • [343. 整数拆分](https://leetcode.cn/problems/integer-break/)
      • 一、题目
      • 二、题解
        • 方法一:动态规划
        • 方法改良


一、题目

给定一个正整数 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

二、题解

方法一:动态规划

好的,让我们按照动态规划的五个步骤来解决这道题目:

步骤一:确认dp数组以及下标的含义

  • dp[i] 表示正整数 i 拆分后可以获得的最大乘积。

步骤二:确认递推公式

  • 对于正整数 i,我们可以把它拆分成两个正整数 j 和 i-j,其中 1 <= j < i。
  • 那么,对于拆分的两个正整数 j 和 i-j,可以计算它们的乘积 max(j * (i-j))。
  • 但我们还需要考虑 j 和 i-j 是否继续拆分,因此递推公式为 dp[i] = max(max(j * (i-j), j * dp[i-j]), max(dp[j] * (i-j), dp[j] * dp[i-j]))。

步骤三:数组初始化

  • dp[1] 和 dp[2] 的值分别为 0 和 1,因为它们都不能再拆分。

步骤四:确定遍历顺序

  • 我们从小到大遍历正整数 i,从 3 开始遍历到 n,依次计算 dp[i] 的值。

步骤五:举例推导dp数组
让我们通过一个示例来推导 dp 数组。假设输入 n = 6:

进行推导:

  1. 初始化 dp 数组:
dp = [0, 1]
  1. 计算 dp[3]:
dp[3] = max(max(1*(3-1), 1*dp[3-1]), max(dp[1]*(3-1), dp[1]*dp[3-1])) = max(max(1*2, 1*1), max(0*2, 0*1)) = 2
  1. 计算 dp[4]:
dp[4] = 4
  1. 计算 dp[5]:
dp[5] = 6
  1. 计算 dp[6]:
dp[6] = 9

最终返回 dp[n],即 dp[6] = 9,表示将正整数 6 拆分后可以获得的最大乘积为 9。

class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[1] = 0;dp[2] = 1;for(int i = 3; i <= n; i++){int maxm = 1;//i/2是一个改善措施,因为当j>i/2后所有的情况之前都已经产生过了for(int j = 1; j <= i/2; j++){int k = i-j;int temp = max(max(j*k,dp[j]*k),max(dp[k]*j,dp[j]*dp[k]));if(maxm < temp) maxm = temp;}dp[i] = maxm;}return dp[n];}
};

方法改良

在递推公式的计算部分,我们可以将递推公式简化为 dp[i] = max(j * k, j * dp[k]),并且不再计算 dp[j] * dp[k] 部分。

改良的原因:

  • 在原始的递推公式中,我们考虑了 j 和 k 是否继续拆分,计算了 dp[j] * dp[k] 部分,但实际上,这部分是在之前的状态中已经计算过的,而且不会再参与当前状态的计算。
  • 因此,我们可以直接在递推公式中计算 j * dp[k] 部分,而不再重复计算之前已经得到的 dp[j]。

改良后的代码如下:

cppCopy codeclass Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[2] = 1;for (int i = 3; i <= n; i++) {int maxm = 1;for (int j = 1; j <= i / 2; j++) {int k = i - j;int temp = max(j * k, j * dp[k]);if (maxm < temp) maxm = temp;}dp[i] = maxm;}return dp[n];}
};

相关文章:

LeetCode343. 整数拆分

343. 整数拆分 文章目录 [343. 整数拆分](https://leetcode.cn/problems/integer-break/)一、题目二、题解方法一&#xff1a;动态规划方法改良 一、题目 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整…...

单机,集群和分布式概念

单机的局限性&#xff1a; 1.受限于硬件资源&#xff0c;单机所能承受的用户并发量太少&#xff1b; 2.一个系统有多个模块&#xff0c;任意模块的修改都会导致整个项目代码重新编译、部署&#xff1b; 3.系统中&#xff0c;有些模块是CPU密集型&#xff0c;有些模块是I/O密…...

小目标检测(1)——大恒(DaHeng)相机操作与控制编程

文章目录 引言正文相关开发库的介绍编程准备配置引用头文件GalaxyIncludes.h配置lib文件 具体编程过程初始化和反初始化枚举设备开关设备 属性控制属性控制器种类 图像采集控制和图像处理采单帧回调采集图像处理流对象属性控制 获取设备事件获取掉线事件通知 样例程序分析补充&…...

异步实现邮件发送

目录 问题描述&#xff1a; 问题分析&#xff1a; 问题解决&#xff1a; 分析总结&#xff1a; 问题描述&#xff1a; 在写接口的时候&#xff0c;遇到一个问题&#xff0c;前端要求直接返回结果再去运行其他代码。 问题分析&#xff1a; 因为经费紧张&#xff0c;本次使用…...

【Redis】内存数据库Redis进阶(Redis分片集群)

目录 分布式缓存 Redis 四大问题搭建Redis分片集群分片原理散列插槽&#xff08;插槽原理&#xff09;集群伸缩需求设定配置集群伸缩 故障转移自动故障转移手动故障转移 RedisTemplate访问分片集群 分布式缓存 Redis 四大问题 基于 Redis 集群解决单机 Redis 存在的四大问题&a…...

替代LT8711龙讯替代RTD2172 CS5265中文规格书4K60HZ转接线 设计Type-C转HDMI2.0高清投屏方案

龙迅LT8711是一款Type-C/DP1.2 to HDMI2.0方案芯片&#xff0c;北京集睿致远&#xff08;ASL&#xff09;推出的CS5265可以完全代替LT8711UX&#xff0c;封装尺寸比LT8711UX小的同时&#xff0c;CS5265的芯片集成度高&#xff0c;内置MCU&#xff0c;内置lLDO等&#xff0c;CS5…...

HCIA-datacom数通题库和录播视频资料

HCIA-Datacom&#xff0c;是华为数通认证的初级考试&#xff0c;培训与认证具备数通基础通用知识和技能水平的工程师&#xff0c;只是入门了解数通的一些基础通用知识&#xff0c;适用于小白了解和学习数通知识点起点。 个人建议还是有必要考的&#xff0c;如果在企业考试考试…...

优思学院|质量工程师应具备什么能力?

质量工程师是一个需要耐心、细心、坚持态度、沟通能力、协调能力的工作&#xff0c;更需要持续学习强化自身的专业知识。 质量工程师负责审核、客户投诉的调查、过程的改进以达到质量之提升&#xff0c;他們也必须要预警生产线风险、质量异常&#xff0c;并且协调不同的部門一…...

数据分析 VS 数据可视化:决战时刻

数据分析和数据可视化是数据科学领域中两个重要的组成部分&#xff0c;很多人不明白两者之间的关系&#xff0c;会误认为是一个东西&#xff0c;其实不然。本文就带大家简单了解一下它们的区别与联系吧&#xff01; 数据分析是指通过收集、处理和解释数据来获取有关特定问题或…...

Vue3中无法为el-tree-select设置反选问题分析

环境&#xff1a;Vue3.2、Element Plus 问题&#xff1a;子组件 setting.vue > 弹窗组件 Dialog > 树选择组件el-tree-select &#xff0c;无法设置默认选中项 default-checked-keys 场景&#xff1a;在一个后台系统的列表页&#xff0c;选中一行数据&#xff0c;点击设置…...

Redis - 缓存持久化

Redis 的缓存持久化有两种技术 &#xff1a; RDB 和 AOF RDB Redis 的数据快照 简单说就是将缓存中的所有数据都记录到磁盘中&#xff0c;当Redis发生故障的时候&#xff0c;只需读取快照文件&#xff0c;就可恢复数据 相应的命令是 save 和 bgsave &#xff0c;这两个命名…...

Pandas进阶修炼120题-第三期(金融数据处理,51-80题)

目录 往期内容&#xff1a;第一期&#xff1a;Pandas基础&#xff08;1-20题&#xff09;第二期&#xff1a;Pandas数据处理&#xff08;21-50题&#xff09; 第三期 金融数据处理51.使用绝对路径读取本地Excel数据方法一&#xff1a;双反斜杠绝对路径方法二&#xff1a;r 拓展…...

3、HAproxy高级配置

基于cookie的会话保持 在 HAProxy 中&#xff0c;可以通过使用 cookie 配置来实现基于 Cookie 的会话保持。cookie 配置用于配置与会话保持相关的选项&#xff0c;允许您定义要在HTTP响应中插入或重写的Cookie以及其他与Cookie会话保持相关的参数。 以下是一些常用的 cookie 配…...

tcpdump网络抓包工具的使用

tcpdump 是一款用在linux系统上的网络抓包工具 1、 基本语法 tcpdump 的常用参数如下&#xff1a; tcpdump -i eth0 -nn -s0 -v port 80-i : 选择要捕获的接口&#xff0c;通常是以太网卡或无线网卡&#xff0c;也可以是 vlan 或其他特殊接口。如果该系统上只有一个网络接口&…...

AMEYA360旗下品牌:日本SUSUMU推出RGV系列贴片电阻器新产品

电动汽车、机器人、精密测量仪器——在上述三例应用领域中&#xff0c;具有高精度、坚固性和长期稳定性的组件是必不可少的。对于这些和类似的应用&#xff0c;RGV系列精密电阻器是理想的选择。 RGV系列电阻器 RGV系列金属薄膜贴片电阻器的电阻值范围为120kΩ至3MΩ&#xff08…...

git-版本控制器

集中式版本控制工具&#xff08;不常用&#xff09; 版本库集中于中央服务器&#xff0c;team要联网才能工作&#xff08;下载代码&#xff09; SVN CVS 分布式版本控制工具 每个电脑上都有一个完整的版本库&#xff0c;工作时无需联网&#xff0c;可以把修改推送给其他人来…...

台式机/工控机通过网线共享笔记本电脑无线网络linux系统下 usb网卡的驱动安装

一、台式机/工控机通过网线共享笔记本电脑无线网络 1、 将台式机通过网线和笔记本连接。 2、 将笔记本的“本地连接”和“无线网络连接”的ipv4均设置为自动获取。 4.修改台式机的IP地址为如下&#xff08;对应笔记本信息&#xff09; IP地址为192.168.XXX.12 子网掩码为255.2…...

kotlin 编写一个简单的天气预报app(五)增加forcast接口并显示

参考资料 OpenWeatherMap提供了一个/forecast接口&#xff0c;用于获取未来几天的天气预报。你可以使用HTTP GET请求访问该接口&#xff0c;并根据你所在的城市或地理坐标获取相应的天气数据。 以下是一个示例请求的URL和一些常用的参数&#xff1a; URL: http://api.openwe…...

vs调试引发了异常:读取访问权限冲突,argv是0x7

vs2019写了几句小代码&#xff0c;结果报错&#xff1a; 引发了异常:读取访问权限冲突,argv是0x7 查了一堆是什么数组越界了&#xff0c;空指针异常了啥的。 只好都注释掉只留下主函数&#xff0c;结果还是报错&#xff0c;定睛一看才发现原因&#xff1a;main函数忘写第一…...

【电影推荐系统】实时推荐

概览 技术方案&#xff1a; 日志采集服务&#xff1a;通过利用Flume-ng对业务平台中用户对于电影的一次评分行为进行采集&#xff0c;实时发送到Kafka集群。消息缓冲服务&#xff1a;项目采用Kafka作为流式数据的缓存组件&#xff0c;接受来自Flume的数据采集请求。并将数据推…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...