代码随想录第40天|343. 整数拆分

343. 整数拆分 

343. 整数拆分 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

动态规划,本题关键在于理解递推公式!| LeetCode:343. 整数拆分_哔哩哔哩_bilibili

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

动规五部曲:

1、确定dp数组以及下标的含义:分拆数字i可以得到的最大乘积为dp[i];

2、确定递推公式:dp[i] 的最大值怎么得到?j*(i-j) 或者 j*dp[i-j];

3、dp的初始化:dp[2]=1;

4、确定遍历顺序:

  // 从正整数 3 开始遍历到 n
        for (int i = 3; i <= n; i++) {
            // 内层循环变量 j 表示拆分的位置,从 1 开始遍历到 i-j,因为 j 最大不会超过 i 的一半
            for (int j = 1; j <= i - j; j++) {
                // 计算将正整数 i 拆分为 j 和 i-j 后的乘积,取两者中的较大值
                // Math.max(j * (i - j), j * dp[i - j]) 表示将正整数 i 拆分成两个数和两个以上的数的情况下的最大乘积
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

5、举例推导dp公式:当n=10:

综合代码:

class Solution {
    public int integerBreak(int n) {
        // 创建一个数组 dp,其中 dp[i] 表示将正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n + 1];
        // 初始化 dp[2],因为题目要求至少拆分成两个正整数,所以 dp[2] 的最大乘积为 1
        dp[2] = 1;
        // 从正整数 3 开始遍历到 n
        for (int i = 3; i <= n; i++) {
            // 内层循环变量 j 表示拆分的位置,从 1 开始遍历到 i-j,因为 j 最大不会超过 i 的一半
            for (int j = 1; j <= i - j; j++) {
                // 计算将正整数 i 拆分为 j 和 i-j 后的乘积,取两者中的较大值
                // Math.max(j * (i - j), j * dp[i - j]) 表示将正整数 i 拆分成两个数和两个以上的数的情况下的最大乘积
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        // 返回将正整数 n 拆分后的结果的最大乘积
        return dp[n];
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/555620.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024-4-18 群讨论:Java Agent,JFR 与 JIT 的一些讨论

以下来自本人拉的一个关于 Java 技术的讨论群。关注公众号&#xff1a;hashcon&#xff0c;私信进群拉你 命令行中带 -XX:StartFlightRecording 启动&#xff0c;同时带 -javaagent&#xff0c;那么谁先启动&#xff1f;jfr能采集到agent启动前后资源消耗情况不&#xff1f; 不…

基于深度学习的手写汉字识别系统(含PyQt+代码+训练数据集)

基于深度学习的手写汉字识别系统&#xff08;含PyQt代码训练数据集&#xff09; 前言一、数据集1.1 数据集介绍1.2 数据预处理 二、模型搭建三、训练与测试3.1 模型训练3.2 模型测试 四、PyQt界面实现参考资料 前言 本项目是基于深度学习网络模型的人脸表情识别系统&#xff0…

c++编程(6)——类与对象(4)运算符重载、赋值重载函数

欢迎来到博主的专栏——C编程 博主ID&#xff1a;代码小豪 文章目录 运算符重载赋值重载函数默认赋值重载函数其他运算符重载函数 运算符重载 重载这个概念在c中已经出现两次了&#xff0c;在前面的文章中&#xff0c;函数重载指的是可以用相同名字的函数实现不同的功能。而运…

【WebSocket连接异常】前端使用WebSocket子协议传递token时,Java后端的正确打开方式!!!

文章目录 1. 背景2. 代码实现和异常发现3. 解决异常3.1 从 URL入手3.2 从 WebSocket子协议的使用方式入手&#xff08;真正原因&#xff09; 4. 总结&#xff08;仍然存在的问题&#xff09; 前言&#xff1a; 本篇文章记录的是使用WebSocket进行双向通信时踩过的坑&#xff0c…

将gdip-yolo集成到yolov9模型项目中(支持预训练的yolov9模型)

1、yolov9模型概述 1.1 yolov9 YOLOv9意味着实时目标检测的重大进步&#xff0c;引入了可编程梯度信息&#xff08;PGI&#xff09;和通用高效层聚合网络&#xff08;GELAN&#xff09;等开创性技术。该模型在效率、准确性和适应性方面取得了显著改进&#xff0c;在MS COCO数…

「 安全工具介绍 」软件成分分析工具Black Duck,业界排名TOP 1的SCA工具

在现代的 DevOps 或 DevSecOps 环境中&#xff0c;SCA 激发了“左移”范式的采用。提早进行持续的 SCA 测试&#xff0c;使开发人员和安全团队能够在不影响安全性和质量的情况下提高生产力。前期在博文《「 网络安全常用术语解读 」软件成分分析SCA详解&#xff1a;从发展背景到…

Qt-饼图示范

1.效果图 2.代码如下 2.1 .h文件 #ifndef PIECHARTWIDGET_H #define PIECHARTWIDGET_H#include <QWidget> #include <QChartView> #include <QPieSeries>#include<QVBoxLayout> #include<QMessageBox> #include <QtCharts>struct PieDat…

FastAPI - uvicorn设置 logger 日志格式

怎么将日志打印到文件 在main.py加入log_config“./uvicorn_config.json” import uvicornif __name__ "__main__":uvicorn.run("app:app", host"0.0.0.0", port8000, log_config"./uvicorn_config.json")uvicorn_config.json {&qu…

“互联网+”创意创业大赛活动方案

大赛历时6个月&#xff0c;总体分两个赛程&#xff1a;一是策划创意阶段。评审的是方案。二是组织实施阶段。通过阶段一立项的项目由公司协助实施&#xff0c;最终评审的是项目落实情况。学生可两个赛程单独参加&#xff0c;也可连续参加。 具体流程及时间安排如下&#xff1a;…

ansible-tower连接git实现简单执行playbook

前提&#xff1a;安装好ansible-tower和git&#xff0c;其中git存放ansible得剧本 其中git中得内容为&#xff1a; --- - name: yjxtesthosts: yinremote_user: rootgather_facts: noroles:- testroles/test/tasks/main.yml #文件内容 --- #- name: Perform Test Task # tas…

单链表-通讯录

目录 单链表实现 通讯录代码实现 初始化 初始化函数 添加 删除 展示 查找 修改 销毁 代码展示 main.c text.c text.h list.c list.h 和前面的通讯录实现差不多这次就是实现一个以单链表为底层的通讯录 单链表实现 数据结构&#xff1a;单链表-CSDN博客 通讯…

OpenHarmony多媒体-video_trimmer

简介 videotrimmer是在OpenHarmony环境下&#xff0c;提供视频剪辑能力的三方库。 效果展示&#xff1a; 安装教程 ohpm install ohos/videotrimmerOpenHarmony ohpm环境配置等更多内容&#xff0c;请参考 如何安装OpenHarmony ohpm包 。 使用说明 目前支持MP4格式。 视频…

docker部署的nginx配置ssl证书https

申请ssl证书&#xff0c;已腾讯的免费证书为例 2.上传证书到linux服务器 2.1 映射ssql目录 首先确保容器命令已映射宿主机目录&#xff0c;不一定是ssl&#xff0c;也可以是其他路径。 2.2 上传文件到指定路径 以我映射的ssl路径为例&#xff0c;我上传到宿主机的 /usr/local…

【GEE实践应用】使用MODIS NDVI数据集绘制研究区域每日NDVI序列曲线

// 设置研究区域 var geometry table;// 选择MODIS NDVI 数据集 var modisNDVI ee.ImageCollection(MODIS/006/MOD13A2).filterBounds(geometry).filterDate(2000-01-01, 2023-12-31);// 计算每天的平均 NDVI var dailyMeanNDVI modisNDVI.map(function(image) {var date e…

(最详细)关于List和Set的区别与应用

关于List与Set的区别 List和Set都继承自Collection接口&#xff1b; List接口的实现类有三个&#xff1a;LinkedList、ArrayList、Vector。Set接口的实现类有两个&#xff1a;HashSet(底层由HashMap实现)、LinkedHashSet。 在List中&#xff0c;List.add()是基于数组的形式来添…

OpenHarmony网络组件-Mars

项目简介 Mars 是一个跨平台的网络组件&#xff0c;包括主要用于网络请求中的长连接&#xff0c;短连接&#xff0c;是基于 socket 层的解决方案&#xff0c;在网络调优方面有更好的可控性&#xff0c;暂不支持HTTP协议。 Mars 极大的方便了开发者的开发效率。 效果演示 编译…

简述Kafka的高可靠性

什么叫可靠性&#xff1f; 大家都知道&#xff0c;系统架构有三高&#xff1a;「高性能、高并发和高可用」&#xff0c;三者的重要性不言而喻。 对于任意系统&#xff0c;想要同时满足三高都是一件非常困难的事情&#xff0c;大型业务系统或者传统中间件都会搭建复杂的架构来…

万字长文带你APK反编译重签名aabapks转换

Android反编译 反编译&#xff08;Decompilation&#xff09;是将已编译的程序&#xff08;比如二进制代码&#xff09;转换回更高级别的编程语言代码的过程。这通常用于理解程序的工作原理&#xff0c;进行软件审计&#xff0c;恢复丢失的源代码&#xff0c;或者进行教学研究…

提升数据质量的三大要素:清洗prompt、数据溯源、数据增强(含Reviewer2和PeerRead)​

前言 我带队的整个大模型项目团队超过40人了&#xff0c;分六个项目组 每个项目组都是全职带兼职&#xff0c;且都会每周确定任务/目标/计划然后各项目组各自做任务拆解&#xff0c;有时同组内任务多时 则2-4人一组 方便并行和讨论&#xff0c;每周文档记录当周工作内容&…

Leetcode 4.18

Leetcode 1.无重复字符的最长子串2.最长回文子串3.整数反转4.字符串转换整数 (atoi)5.正则表达式匹配 1.无重复字符的最长子串 无重复字符的最长子串 滑动窗口&#xff0c;先让右指针右移&#xff0c;如果发现这个子串有元素和右指针当前元素重复。 则&#xff1a; 左指针右移…