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 ,将其拆分为 k 个 正整数 的和( k > 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。 示例 2: 输入: n 10 输出: 36 解释: 1…...
【MATLAB源码-第180期】基于matlab的PTS,SLM,CPFilter三种降低OFDM系统的PAPR仿真。
操作环境: MATLAB 2022a 1、算法描述 1. 限幅和滤波(Clipping and Filtering) 原理简介 限幅和滤波是一种基础且直观的方法,用于降低OFDM信号的PAPR。在限幅阶段,信号的幅度在达到设定阈值时会被削减,…...
学透Spring Boot — 004. Spring Boot Starter机制和自动配置机制
如果你项目中一直用的是 Spring Boot,那么恭喜你没有经历过用 Spring 手动集成其它框架的痛苦。 都说 Spring Boot 大大简化了 Spring 框架开发 Web 应用的难度,这里我们通过配置 Hibernate 的两种方式来深刻体会这一点: 使用 Spring 框架集…...
面试算法-170-二叉树的最大深度
题目 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:3 解 class Solution {public int maxDepth(TreeNod…...
【数据结构】哈希
文章目录 1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决4.1 闭散列4.2 开散列 unordered 系列的关联式容器之所以效率比较高,是因为其底层使用了哈希结构。 1. 哈希概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系ÿ…...
Kubernetes(k8s)监控与报警(qq邮箱+钉钉):Prometheus + Grafana + Alertmanager(超详细)
Kubernetes(k8s)监控与报警(qq邮箱钉钉):Prometheus Grafana Alertmanager(超详细) 1、部署环境2、基本概念简介2.1、Prometheus简介2.2、Grafana简介2.3、Alertmanager简介2.4、Prometheus …...
STM32-04基于HAL库(CubeMX+MDK+Proteus)中断案例(按键中断扫描)
文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式,生成代码四、MDK打开生成项目,编写HAL库的按键检测代码五、运行仿真程序,调试代码 一、功能需求分析 在完成GPIO输入输出案例之后,开始新的功能…...
第十五篇:Mybatis
文章目录 一、什么是MyBatis二、Mybatis入门案例三、配置SQL提示四、数据库连接池四、lombok五、mybatis基础操作5.1 根据id删除5.2 预编译SQL5.3 新增员工5.4 更新员工5.5 查询员工(用于页面回显)5.6 条件查询 七、XML映射文件八、动态SQL8.1 if语句8.2…...
【MacBook系统homebrew镜像记录】
安装 使用Homebrew 国内源安装脚本,贼方便: /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"切换至清华大学镜像源: 命令合并: 分别切换了 brew.git、 homebrew-core.git、 homebrew-…...
深拷贝总结
JSON.parse(JSON.stringify(obj)) 这行代码的运行过程,就是利用 JSON.stringify 将js对象序列化(JSON字符串),再使用JSON.parse来反序列化(还原)js对象;序列化的作用是存储和传输。(…...
RabbitMQ在云原生环境中部署和应用实践
一、RabbitMQ和云原生技术的关系 RabbitMQ是一种开源的、实现了先进的消息队列协议(AMQP)的消息队列软件。而云原生技术就是为在公共云、私有云以及其他各种云环境提供应用的一种方法。RabbitMQ和云原生技术在分布式系统和微服务架构中都起到了关键作用…...
flask 后端 + 微信小程序和网页两种前端:调用硬件(相机和录音)和上传至服务器
选择 flask 作为后端,因为后续还需要深度学习模型,python 语言最适配;而 flask 框架轻、学习成本低,所以选 flask 作为后端框架。 微信小程序封装了调用手机硬件的 api,通过它来调用手机的摄像头、录音机,…...
蓝桥杯嵌入式(G431)备赛笔记——ADC+LCD
目录 题目要求(真题): cubeMX配置: 小试牛刀: Keil代码: 效果演示: 题目要求(真题): 使用第十一届第二场真题,练习ADC波部分的代码 cubeMX配…...
最近公共祖先(LCA)
题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 N,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 N−1 行每行包含两个正整数x,y,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以…...
ABBYY FineReader15免费电脑OCR图片文字识别软件
产品介绍:ABBYY FineReader 15 OCR图片文字识别软件 ABBYY FineReader 15是一款光学字符识别(OCR)软件,专门设计用于将扫描的文档、图像和照片中的文本转换成可编辑和可搜索的格式。这款软件利用先进的OCR技术,能够识别…...
2024年第十七届 认证杯 网络挑战赛 (A题)| 保暖纤维的保暖能力 |数学建模完整代码+建模过程全解全析
当大家面临着复杂的数学建模问题时,你是否曾经感到茫然无措?作为2022年美国大学生数学建模比赛的O奖得主,我为大家提供了一套优秀的解题思路,让你轻松应对各种难题。 让我们来看看认证杯 网络挑战赛 (A题)!…...
算法训练营第37天|LeetCode 738.单调递增的数字 968.监控二叉树
LeetCode 738.单调递增的数字 题目链接: LeetCode 738.单调递增的数字 解题思路: 从后向前遍历,当不满足递增条件时,当前位置赋值为9,前一位减一。之后记录不满足位置,将后续全部赋值为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 …...
大恒相机-程序异常退出后显示被占用
心跳时间代表多久向相机发送一次心跳包,如果超时则设备会认为断开了,停止工作并主动释放占用资源。 在相机打开后添加代码: #ifdef _DEBUG//设置心跳超时时间 3sObjFeatureControlPtr->GetIntFeature("GevHeartbeatTimeout")-&…...
头歌-机器学习 第16次实验 EM算法
第1关:极大似然估计 任务描述 本关任务:根据本节课所学知识完成本关所设置的选择题。 相关知识 为了完成本关任务,你需要掌握: 什么是极大似然估计; 极大似然估计的原理; 极大似然估计的计算方法。 什么是极大似然估计 没有接触过或者没有听过”极大似然估计“的同学…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
