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];
    }
}
相关文章
|
机器学习/深度学习 算法 计算机视觉
Yolov5 + 界面PyQt5 +.exe文件部署运行
Yolov5 + 界面PyQt5 +.exe文件部署运行
|
11月前
|
机器学习/深度学习 人工智能 搜索推荐
AI在医疗领域的革命:智能诊断系统的未来
在科技日新月异的今天,人工智能(AI)技术正逐渐渗透到我们生活的每一个角落,其中医疗领域尤为显著。本文将探讨AI在医疗诊断中的应用及其带来的变革,重点介绍智能诊断系统的发展现状与未来趋势。通过深入浅出的方式,我们将揭示AI如何改变传统医疗模式,提高诊断效率和准确性,最终造福广大患者。
|
机器学习/深度学习 人工智能 算法
探索AI在医疗诊断中的应用:挑战与机遇
本文旨在探讨人工智能(AI)在医疗诊断领域的应用,分析其在提高诊断效率和准确性方面的潜力。同时,讨论了当前面临的挑战,包括数据隐私、算法透明度以及技术普及等问题。通过案例研究,本文展示了AI如何在实际医疗场景中提供辅助诊断,并提出了相应的解决策略。
|
安全 Linux
Linux查看和剔除当前登录用户详细教程
Linux查看和剔除当前登录用户详细教程
333 0
Linux查看和剔除当前登录用户详细教程
|
小程序 前端开发 定位技术
简单快速搭建出适配于多平台的小程序
随着移动互联网的深入发展,小程序以其轻量、便捷、即用即走的特点,逐渐成为企业与用户沟通的重要桥梁。在当今数字化时代,随着各大平台纷纷推出小程序,小程序已成为企业与用户交互的重要工具,跨平台开发更是成为开发者们关注的焦点。作为开发者来说,为了满足不同用户的需求,我们需要能够快速搭建出适配于多平台的小程序,那么本文就来聊一聊小程序的优势、如何实现一站式开发多平台的小程序,以及对于小程序功能模块集成能力的期望。
367 1
简单快速搭建出适配于多平台的小程序
|
JavaScript Java 测试技术
流浪动物救助微信小程序+springboot+vue.js附带文章和源代码设计说明文档ppt
流浪动物救助微信小程序+springboot+vue.js附带文章和源代码设计说明文档ppt
173 2
|
机器学习/深度学习 人工智能 安全
Gandalf AI 通关详解(大模型安全)
Gandalf AI 通关详解(大模型安全)
RPA数字员工:降本增效的智能利器
【1月更文挑战第6天】RPA数字员工:降本增效的智能利器
398 1
RPA数字员工:降本增效的智能利器
|
消息中间件 运维 容灾
理想汽车大规模 Apache RocketMQ 集群部署最佳实践
十年铸剑,Apache RocketMQ 的成长离不开全球接近 500 位开发者的积极参与贡献,相信在下个版本你就是 Apache RocketMQ 的贡献者,在社区不仅可以结识社区大牛,提升技术水平,也可以提升个人影响力,促进自身成长。
867 78
理想汽车大规模 Apache RocketMQ 集群部署最佳实践