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

LeetCode:343. 整数拆分

跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的!
代码随想录

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。

  • dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]))这里面包含了拆成2个数和3个及以上的数的乘积,比如n = 4时拆成2 * 2时最大,当n = 10时拆成 3 * 3 *4 时最大
  • 注意:Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));中是 j * dp[i - j])而不是dp[j] * dp[i - j],后者是至少拆分成4个数的乘机了,注意dp[i]的定义
  • 为什么不拆分dp[j]

    dp【j】*dp【i-j】
    =dp【j-a】*dp【a】dp【i-j】
    =dp【j-a】
    (dp【a】*dp【i-j】)
    =dp【j-a】*dp【i-j+a】
    而又是从1开始的,dp【j-a】*dp【i-j+a】 前面肯定出现固定,所以不需要重复考虑
    e.g. 当i = 10时,
    拆分成: 1 * 9, 2 * 8…
    dp[1] * dp[9], dp[2] * dp[8]…
    如果还拆分dp[2]的话,则:1 * 1 * dp[8],而这种情况是能从dp[1] * dp[9]中拆分出来的;
    而且假设拆分dp[j] 则会落下3个数时候的乘积

	public 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; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

http://www.kler.cn/a/524922.html

相关文章:

  • C++并发编程指南05
  • PostgreSQL 约束
  • 论文阅读(十四):贝叶斯网络在全基因组DNA甲基化研究中的应用
  • 【Jave全栈】Java与JavaScript比较
  • wordpress代码结构解析
  • 海外问卷调查渠道查如何设置:最佳实践+示例
  • MyBatis 框架:简化 Java 数据持久化的利器
  • LLM:BERT or BART 之BERT
  • Vue3 结合 .NetCore WebApi 前后端分离跨域请求简易实例
  • JavaScript_02 表单
  • UE AController
  • Go语言的栈空间管理
  • 使用 Confluent Cloud 的 Elasticsearch Connector 部署 Elastic Agent
  • 全面解析文件包含漏洞:原理、危害与防护
  • 力扣动态规划-14【算法学习day.108】
  • 电子电气架构 --- 车载电子和软件架构概述
  • 完美世界C++游戏开发面试题及参考答案
  • 服务器虚拟化技术详解与实战:架构、部署与优化
  • go gin配置air
  • Time Constant | RC、RL 和 RLC 电路中的时间常数
  • JavaScript系列(49)--游戏引擎实现详解
  • 128周二复盘(164)学习任天堂
  • MIMIC-IV数据部署1:数据的准备(博主因手头上还有15+个SCI项目,龟速更新)
  • Linux线程安全
  • unity实现回旋镖函数
  • 【面试】【详解】计算机网络(TCP 三次握手,四次挥手)