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

leetcode 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

解析

dp[i]的定义:分拆数字i可以得到的最大乘积为dp[i]
dp[i]的最大乘积可以通过2种方式得到:
第一种(2个数相乘):
从1开始遍历j,
j*(i-j)—会被多次调用
第二种(多个数相乘)
j*dp[i-j]

dp[i-j]为重叠子问题,会被多次调用比如

dp[5](dp[6-1],dp[7-2]...)dp[7]为dp[2]*dp[5]与dp[3]*dp[4]等的最大值

代码

import java.util.Scanner;public class IntegerSplit {public static int integerBreak(int n) {int[] dp = new int[n+1];dp[2] = 1;for(int i = 3; i <= n; i++){for(int j = 1; j <= i; j++){dp[i] = Math.max(Math.max(j*(i-j), j*dp[i-j]),dp[i]);}}return dp[n];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(integerBreak(n));}
}

dp数组中的每一个元素都是经过一个不断扩大的循环计算出来的。
在这里插入图片描述

相关文章:

leetcode 343. 整数拆分

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

【MATLAB源码-第180期】基于matlab的PTS,SLM,CPFilter三种降低OFDM系统的PAPR仿真。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 1. 限幅和滤波&#xff08;Clipping and Filtering&#xff09; 原理简介 限幅和滤波是一种基础且直观的方法&#xff0c;用于降低OFDM信号的PAPR。在限幅阶段&#xff0c;信号的幅度在达到设定阈值时会被削减&#xff0c;…...

学透Spring Boot — 004. Spring Boot Starter机制和自动配置机制

如果你项目中一直用的是 Spring Boot&#xff0c;那么恭喜你没有经历过用 Spring 手动集成其它框架的痛苦。 都说 Spring Boot 大大简化了 Spring 框架开发 Web 应用的难度&#xff0c;这里我们通过配置 Hibernate 的两种方式来深刻体会这一点&#xff1a; 使用 Spring 框架集…...

面试算法-170-二叉树的最大深度

题目 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3 解 class Solution {public int maxDepth(TreeNod…...

【数据结构】哈希

文章目录 1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决4.1 闭散列4.2 开散列 unordered 系列的关联式容器之所以效率比较高&#xff0c;是因为其底层使用了哈希结构。 1. 哈希概念 顺序结构以及平衡树中&#xff0c;元素关键码与其存储位置之间没有对应的关系&#xff…...

Kubernetes(k8s)监控与报警(qq邮箱+钉钉):Prometheus + Grafana + Alertmanager(超详细)

Kubernetes&#xff08;k8s&#xff09;监控与报警&#xff08;qq邮箱钉钉&#xff09;&#xff1a;Prometheus Grafana Alertmanager&#xff08;超详细&#xff09; 1、部署环境2、基本概念简介2.1、Prometheus简介2.2、Grafana简介2.3、Alertmanager简介2.4、Prometheus …...

STM32-04基于HAL库(CubeMX+MDK+Proteus)中断案例(按键中断扫描)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的按键检测代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 在完成GPIO输入输出案例之后&#xff0c;开始新的功能…...

第十五篇:Mybatis

文章目录 一、什么是MyBatis二、Mybatis入门案例三、配置SQL提示四、数据库连接池四、lombok五、mybatis基础操作5.1 根据id删除5.2 预编译SQL5.3 新增员工5.4 更新员工5.5 查询员工&#xff08;用于页面回显&#xff09;5.6 条件查询 七、XML映射文件八、动态SQL8.1 if语句8.2…...

【MacBook系统homebrew镜像记录】

安装 使用Homebrew 国内源安装脚本,贼方便&#xff1a; /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"切换至清华大学镜像源&#xff1a; 命令合并&#xff1a; 分别切换了 brew.git、 homebrew-core.git、 homebrew-…...

深拷贝总结

JSON.parse(JSON.stringify(obj)) 这行代码的运行过程&#xff0c;就是利用 JSON.stringify 将js对象序列化&#xff08;JSON字符串&#xff09;&#xff0c;再使用JSON.parse来反序列化&#xff08;还原&#xff09;js对象&#xff1b;序列化的作用是存储和传输。&#xff08…...

RabbitMQ在云原生环境中部署和应用实践

一、RabbitMQ和云原生技术的关系 RabbitMQ是一种开源的、实现了先进的消息队列协议&#xff08;AMQP&#xff09;的消息队列软件。而云原生技术就是为在公共云、私有云以及其他各种云环境提供应用的一种方法。RabbitMQ和云原生技术在分布式系统和微服务架构中都起到了关键作用…...

flask 后端 + 微信小程序和网页两种前端:调用硬件(相机和录音)和上传至服务器

选择 flask 作为后端&#xff0c;因为后续还需要深度学习模型&#xff0c;python 语言最适配&#xff1b;而 flask 框架轻、学习成本低&#xff0c;所以选 flask 作为后端框架。 微信小程序封装了调用手机硬件的 api&#xff0c;通过它来调用手机的摄像头、录音机&#xff0c;…...

蓝桥杯嵌入式(G431)备赛笔记——ADC+LCD

目录 题目要求&#xff08;真题&#xff09;&#xff1a; cubeMX配置&#xff1a; 小试牛刀&#xff1a; Keil代码&#xff1a; 效果演示&#xff1a; 题目要求&#xff08;真题&#xff09;&#xff1a; 使用第十一届第二场真题&#xff0c;练习ADC波部分的代码 cubeMX配…...

最近公共祖先(LCA)

题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 N,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 N−1 行每行包含两个正整数x,y,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以…...

ABBYY FineReader15免费电脑OCR图片文字识别软件

产品介绍&#xff1a;ABBYY FineReader 15 OCR图片文字识别软件 ABBYY FineReader 15是一款光学字符识别&#xff08;OCR&#xff09;软件&#xff0c;专门设计用于将扫描的文档、图像和照片中的文本转换成可编辑和可搜索的格式。这款软件利用先进的OCR技术&#xff0c;能够识别…...

2024年第十七届 认证杯 网络挑战赛 (A题)| 保暖纤维的保暖能力 |数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2022年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题。 让我们来看看认证杯 网络挑战赛 (A题&#xff09;&#xff01…...

算法训练营第37天|LeetCode 738.单调递增的数字 968.监控二叉树

LeetCode 738.单调递增的数字 题目链接&#xff1a; LeetCode 738.单调递增的数字 解题思路&#xff1a; 从后向前遍历&#xff0c;当不满足递增条件时&#xff0c;当前位置赋值为9&#xff0c;前一位减一。之后记录不满足位置&#xff0c;将后续全部赋值为9. 代码&#x…...

Vue+el-table 修改表格 单元格横线边框颜色及表格空数据时边框颜色

需求 目前 找到对应的css样式进行修改 修改后 css样式 >>>.el-table th.el-table__cell.is-leaf {border-bottom: 1px solid #444B5F !important;}>>>.el-table td.el-table__cell,.el-table th.el-table__cell.is-leaf {border-bottom: 1px solid #444B5F …...

大恒相机-程序异常退出后显示被占用

心跳时间代表多久向相机发送一次心跳包&#xff0c;如果超时则设备会认为断开了&#xff0c;停止工作并主动释放占用资源。 在相机打开后添加代码&#xff1a; #ifdef _DEBUG//设置心跳超时时间 3sObjFeatureControlPtr->GetIntFeature("GevHeartbeatTimeout")-&…...

头歌-机器学习 第16次实验 EM算法

第1关:极大似然估计 任务描述 本关任务:根据本节课所学知识完成本关所设置的选择题。 相关知识 为了完成本关任务,你需要掌握: 什么是极大似然估计; 极大似然估计的原理; 极大似然估计的计算方法。 什么是极大似然估计 没有接触过或者没有听过”极大似然估计“的同学…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

云原生时代的系统设计:架构转型的战略支点

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、云原生的崛起&#xff1a;技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深&#xff0c;传统的 I…...