当前位置: 首页 > 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 过程参考模型...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...