首页 > 其他分享 >力扣343 整数拆分

力扣343 整数拆分

时间:2023-02-24 18:12:46浏览次数:34  
标签:正整数 乘积 int 力扣 拆分 343 dp

题目:

给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

示例:

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

思路:

硬推:从n=1到n=10一一举例,会发现是S(4)是第一个超过它本身数字大小的数,所以当后续的加数种出现4以上的数字,就要用S(4)去取代这个数字本身相乘。

比较暴力的解法就是:

class Solution {
    public int integerBreak(int n) {
        //1.dp数组定义:dp[i]:给定正整数i可得到的最大乘积
        int[] dp=new int[n+2];
        //2.初始化
        dp[0]=1;
        dp[1]=2;
        dp[2]=4;
        dp[3]=6;
        if(n>2){
            dp[4]=9;
        }
        //3.递推公式dp[i]=dp[i-3]*3
        //4.遍历顺序
        for(int i=5;i<=n;i++){
            dp[i]=dp[i-3]*3;
        }
        //5.举例验证
        return dp[n-2];
    }
}

 代码随想录给出的解法:

class Solution {
    public int integerBreak(int n) {
        //dp[i] 为正整数 i 拆分后的结果的最大乘积
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            for(int j = 1; j <= i-j; j++) {
                // 这里的 j 其实最大值为 i-j,再大只不过是重复而已,
                //并且,在本题中,我们分析 dp[0], dp[1]都是无意义的,
                //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ,再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
            }
        }
        return dp[n];
    }
}

 

 

标签:正整数,乘积,int,力扣,拆分,343,dp
From: https://www.cnblogs.com/cjhtxdy/p/17152692.html

相关文章

  • Java力扣
    目录JZ6从尾到头打印链表JZ24反转链表JZ25合并两个排序的链表JZ52两个链表的第一个公共结点JZ23链表中环的入口结点JZ6从尾到头打印链表JZ24反转链表JZ25合并......
  • 翻转数组(力扣)
    题目:给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1......
  • 微服务拆分治理最佳实践
    作者:京东零售徐强黄威张均杰背景部门中维护了一个老系统,功能都耦合在一个单体应用中(300+接口),表也放在同一个库中(200+表),导致系统存在很多风险和缺陷。经常出现问题:如......
  • 力扣63 不同路径2
    题目:一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi......
  • 力扣62 不同路径
    题目:一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“F......
  • 力扣——《数据结构·入门篇》刷题笔记
    第一天-数组  1️⃣存在重复元素  题目:给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。 ......
  • HTTP拆分响应攻击
    HTTP拆分响应攻击CRLF指的是回车符(CR,ASCII13,\r,%0d)和换行符(LF,ASCII10,\n,%0a)的简称(\r\n)。在HTTP报文中,HTTPHeader每个字段以一个CRLF分隔;HTTPHeader与HTTPBody以两个C......
  • 力扣746 使用最小花费爬楼梯
    题目:给你一个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下标......
  • 微服务拆分治理最佳实践
    作者:京东零售徐强黄威张均杰背景部门中维护了一个老系统,功能都耦合在一个单体应用中(300+接口),表也放在同一个库中(200+表),导致系统存在很多风险和缺陷。经常出现问题......
  • 【力扣】:N字型
    1classSolution{2publicStringconvert(Strings,intnumRows){3StringresultS="";//待返回的字符串4intlen......