06_整数拆分

简介: 06_整数拆分

343. 整数拆分

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

  • 输入: 2
  • 输出: 1
  • 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

  • 输入: 10
  • 输出: 36
  • 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
  • 说明: 你可以假设 n 不小于 2 且不大于 58。

【思路】

动规五部曲,分析如下:

1、确定dp数组(dp)以及下标的含义

dp[i]:分拆数字i,可以得到的最大乘积为dp[i]。

2、确定递推公式

dp[i]最大乘积得到的方式:

  1. 一个是j*(i-j)直接相乘
  2. 一个是j*dp[i-j],相当于是拆分(i-j)
dp[i] = max(dp[i], max((i-j) * j, dp[i-j]*j));

理解:j * (i - j) 是单纯的把整数拆分为两个数相乘,而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。

3、dp数组的初始化

dp[1]=0,dp[2]=1

4、遍历顺序

从前往后遍历即可

for(int i = 3; i <= n; i++) {
  for(int j = 0; j < i; j++) {
    dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  }
}

进一步的优化

for(int i = 3; i <= n; i++) {
  for(int j = 0; j <= i / 2; j++) {
    dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  }
}

5、举例推导dp数组

import java.util.*;
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[1] = 0;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max((i-j)*j, dp[i-j] * j));
            }
        }
        return dp[n];
    }
}
相关文章
|
JavaScript 前端开发 安全
TypeScript 与 ArkTS 全面对比:鸿蒙生态下的语言演进
本文深入对比TypeScript与华为鸿蒙原生语言ArkTS,从类型系统、UI开发、性能优化到生态定位,全面解析二者差异。ArkTS基于TS演进,面向操作系统层级重构,具备强类型安全、声明式UI、AOT编译与分布式能力,助力“一次开发,多端部署”。结合10亿鸿蒙设备爆发趋势,为开发者提供技术选型指南与平滑迁移路径,是进军全场景智慧生态的关键钥匙。(238字)
1363 1
|
自然语言处理 算法 开发者
通义灵码开发者社区的重要性——反馈与改进
通义灵码开发者社区是用户反馈的重要平台,用户可直接反馈使用中遇到的问题、建议和需求,如代码错误或性能问题。社区还支持通义灵码团队主动征求用户意见,通过调查问卷等形式收集反馈,以优化产品功能和用户体验,解决兼容性和性能等潜在问题,推动产品的持续改进和发展。
通义灵码开发者社区的重要性——反馈与改进
|
存储 缓存 数据库
数据库数据删除策略:硬删除vs软删除的最佳实践指南
在项目开发中,“删除”操作常见但方式多样,主要分为硬删除与软删除。硬删除直接从数据库移除数据,操作简单、高效,但不可恢复;适用于临时或敏感数据。软删除通过标记字段保留数据,支持恢复和审计,但增加查询复杂度与数据量;适合需追踪历史或可恢复的场景。两者各有优劣,实际开发中常结合使用以满足不同需求。
1693 4
|
存储 弹性计算 固态存储
阿里云服务器按量、包月及包年收费价格,云服务器最新活动价格参考
2025年租用阿里云服务器一年多少钱?不同时期阿里云服务器的租用价格不同,2核2G200M轻量应用云服务器特价38元1年起,经济型e实例2核2G3M带宽 40G ESSD Entry云盘特惠价99元1年,通用算力型u1实例2核4G5M带宽80G ESSD Entry云盘特惠价199元1年。2025年阿里云服务器租用价格表如下文所示。
2731 2
阿里云服务器按量、包月及包年收费价格,云服务器最新活动价格参考
|
机器学习/深度学习 数据采集 人工智能
TeleAI 开源星辰语义大模型-TeleChat2!
2024.9.20 中国电信人工智能研究院(TeleAI)开源TeleChat2-115B模型,该模型是首个完全国产算力训练并开源的千亿参数模型。
生物合成材料:生物制造的新材料
【10月更文挑战第19天】生物合成材料是利用生物体系中的生物大分子或通过生物转化过程得到的新型材料,具有良好的生物相容性、可降解性和特定的生物活性。本文介绍了其基本原理、制备技术、应用领域及未来发展趋势,涵盖医疗、环保、农业等多个领域,展示了其广阔的应用前景和巨大潜力。
1190 2
|
负载均衡 数据可视化 API
像素流送api ue多人访问需要什么显卡服务器
本文总结了关于像素流送技术的五大常见问题,包括是否支持Unity模型推流、UE多人访问的最大并发数、所需服务器配置、稳定性问题及API支持情况,旨在帮助开发者更好地理解和应用这一技术。
905 1
|
监控 安全 网络安全
|
边缘计算 网络协议 5G
SRv6 的好处:深入探讨下一代网络技术
【8月更文挑战第28天】
1354 0
SRv6 的好处:深入探讨下一代网络技术