精华内容
下载资源
问答
  • 2021-11-01 09:45:54

    整数拆分

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
    
    示例 1:
    
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
    示例 2:
    
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    说明: 你可以假设 n 不小于 2 且不大于 58。
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/integer-break
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    

    解释:

    首先寻找最优子结构。

    我们通过看问题可以知道这样的计算规则:n = x1 + y,y = x2 + x3。result = x1 * y = x1 * x2 * x3。也就是说要使 result 最大,需要使得 y 最大。这样最优子结构就出来了。

    而我们求 result 的最大值需要去从1开始拼凑,result = max(1*dp[i-1], …) 直到 i 为之,i-1 * dp[1]。

    但是我们的dp[i]拆分成的数为正整数,所以像 3 = 1 * 2 通过上面的递推公式是求不出来的,因为 dp[2] 得不到2(2拆分不成0+2,因为0是非正整数),所以需要加另一个解 result = max(1 * i-1, 2 * i-2…)

    所以综上,递推公式为 f(n) = max1<=j<i(max(j * i-j,j * f(i-j))

    而我们每次遍历j,将result保存在了dp[i]中,所以上式又可以变成:f(n) = max(f(n), j * i-j, j * f(i-j))

    dp table:dp[i],数字i的最大整数拆分积
    递推公式:f(n) = max(f(n), j*(i-j), j*dp[i-j])
    初始化:dp[0] = dp[1] = 1。但是dp[0]与dp[1]是没有意义的,这里只是为了方便求解才初始化成1的。
    遍历顺序:父问题n比子问题n大,所以从前往后遍历
    终止条件:当求解完n可推出。即 i < n + 1
    
    class Solution:
        def integerBreak(self, n: int) -> int:
            dp = [0 for i in range(n + 1)]
            dp[0] = dp[1] = 1
            
            for i in range(2, n + 1):
                for j in range(1, i):
                    dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
                    
            return dp[n]
    
    更多相关内容
  • 把5拆分成若干无序正整数的和(若干可以包含1),请问有多少种拆分方法? 直接用枚举法实现: 5 = 5 5 = 4+1 5 = 3+2 5 = 3+1+1 5 = 2+2+1 5 = 2+1+1+1 5 = 1+1+1+1+1 很显然,结果为7。注意这里5 = 4+1和5=1+4是...
  • 动态规划整数拆分

    2021-08-12 09:58:25
    LeetCode地址:整数拆分 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 ...

    LeetCode地址:整数拆分

    • 给定一个正整数 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[i]是指第i个数将其拆分为至少两个正整数的和,并且使得这些整数的乘积最大化。
      2.确定递推公式
      确定dp[i]的值,需要确定每次减去的值,可以看作是(i-j)*j的值和dp[i-j]*j的最大值与当前dp[i]的值的比较。
      所以dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j)
      3.确定初始化
      这时初始化dp[0]和dp[1]本身是没有意义的,因为本题的n最小值为2,所以应该初始化的是dp[2]=1;
      4.确定遍历顺序
      数组dp需要顺序遍历从3到n,同时也需要确定每次要减去的值。
      5.举例推导dp数组
      时间复杂度O(n^2) 空间复杂度O(n)
    class Solution {
        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-1;j++){
                    dp[i] = Math.max(dp[i],Math.max((i-j)*j,dp[i-j]*j));
                }
            }
            return dp[n];
        }
    }
    
    展开全文
  • 整数拆分-动态规划

    2022-02-10 16:24:02
    给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。 示例 输入: n = 10 输出: 36 算法 dp[i]表示正整数i拆分后的最大乘积 对于一个数有两种拆分情况,拆分成两个...
    • 题目

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

    • 示例

    输入: n = 10
    输出: 36

    • 算法

    dp[i]表示正整数i拆分后的最大乘积
    对于一个数有两种拆分情况,拆分成两个数,拆分成三个及以上个数

    • 代码
    class Solution {
        public int integerBreak(int n) {
            int[] dp = new int[n+1];
            dp[2] = 1;
            for (int i = 3; i < n + 1; i++) {
                for (int j = 1; j < i; j++) {
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i-j]));
                }
            }
            return dp[n];
        }
    }
    
    • 算法

    尽可能拆分3

    • 代码
    public int integerBreak(int n) {
            if (n <= 3) return n-1;
            int res = 1;
            while (n >= 5) {
                n -= 3;
                res *= 3;
            } 
            res *= n;
            return res;
        }
    
    展开全文
  • 343. 整数拆分 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: ...

    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。

    提示:

    2 <= n <= 58
    

    题解

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

    解析

    1、确定dp含义:dp i表示拆分整数i得到的最大乘积为dp i
    2、推导递推关系:数字i可以拆分为i - j 和 j两部分,其中j从1遍历到i-2, i - j从i-1遍历到2(遍历到2是因为dp初始化是从2开始的,详情看后面dp初始化步骤),dp i必然是直接相乘j * (i-j)和 dp相乘j * dp[i-j]中的最大值,又因为求dp i时有两层循环,也就是说求解dp i时可能要进行多次运算,所以在求第二次及之后的同一dp i时需要把上一次循环的dp i也进行一次求max的运算。综上,得dp i = max(dp i, max(j * (i-j), j * dp i-j)) 。其实就是求这三项的最大值,只不过因为java的Max.max方法只有两个参数,所以要写两个max来完成求这三个值最大值的操作
    3、dp初始化:提给条件n从2开始,初始化从dp 2开始,dp 2 = 1
    4、确定遍历顺序:两层循环遍历。i从3到n,j从1到i-2,i-j从i-1到2(这个是关键,动规:dp i可由dp i-1确定,而初始化又是从dp 2开始的)
    5、手动推导或打印dp数组:验证算法的正确性和用于debug

    展开全文
  • 设f(n,k)为将整数n无序拆分成最多不超过k个数之和的方案个数 根据n和k的关系,考虑下面几种情况: (1)当n=1时,不论k的值为多少(k>0),只有一种拆分,即{1}; 显然 f(n,k)=1 (2)当k=1时,不论n的值为...
  • 题目 给定一个正数1,裂开的方法有一种,(1) 给定一个正数2,裂开的方法有两种,(1和1)、 (2) ...动态规划优化状态依赖的技巧 package com.harrison.class12; /** * @author Harrison * @create 2022-03-23-20:22 *
  • 注: 题目: 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。...动态规划 动规五部曲,分析如下: 确定dp数组(dp table)以及下标的含义 dp[i]:分拆数字i,可以得到的最大乘积为dp
  • 整数拆分
  • 一看到题,想到的是:将这个整数从1到n-1遍历,计算j*(n-j),然后每次遍历的时候更新最大乘积,但是发现这样只能是拆分成2个数,显然不可以。 但是,要是我们能知道拆分开的两个数拆分的最大乘积,那不就得到n的...
  • 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 一、示意图 二、解题思路 //如果是动态规划的话 那只能是dp[n]=max(dp[n-1]*1,dp[n-2]*2)..这样子吧 ...
  • 输入n,和k,问将n用1到k...这个题目是个比较明显的动态规划,如果想不到是背包问题,也可以写出状态转移方程如下。用a[i][j]表示考虑到用数j进行拼接时数字i的拼接方法,可以得到状态转移方程如下:a[i][j]=a[i][j-...
  • 这也相当于是整数拆分问题,即把一个整数n拆分为m个数的和。 思路:起初想着能不能用概率论中的知识直接计算,后面发现算不了,只能通过递推公式以及动态规划计算。 设S(n,m)是n个物体分成m堆的方法数,则有递推公式...
  • 整数拆分--动态规划

    千次阅读 2020-07-01 10:48:26
    题目: 将正整数n无序拆分成最大数为m的拆分...由例题可知,顺序不影响结果,我们采用动态规划法来解决问题。建立数组dp[n+1][m+1].其中dp[i][j]指正整数i被拆分为最多j个数字的方案数。注意不是一定要拆为j个而是拆为
  • 使用动态规划解决整数拆分问题。
  • 整数拆分 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: ...
  • 1. 解题思路 #include <bits/stdc++.h> #define MAXN 500 int dp[MAXN][MAXN]; using namespace std; void Split(int p, int q) { for (int n = 1; n <= p; n++) ... k++...
  • 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。 返回你可以获得的最大乘积 。 class Solution { public: int integerBreak(int n) { if(n == 2) return 1; ...
  • 1.将正整数n无序拆分成最大数为m的拆分方案个数,要求所有拆分方案不重复。样例:n = 5, m = 5,对应的拆分方案如下:5 = 55 = 4 + 15 = 3 + 25 = 3 + 1 + 15 = 2 + 2 + 15 = 2 + 1 + 1 + 15 = 1 + 1 + 1 + 1 + 1分析...
  • 343. 整数拆分 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释...
  • //dp[2]是指数组的初始化,因为dp[1]拆分的结果也是1,所以直接用dp[2] dp[2]=1; for(int i=3;i<=n;i++){ for(int j=1;j<i-1;j++) dp[i]=Math.Max(Math.Max(j*(i-j),j*dp[i-j]),dp[i]);//...
  • 动态规划求解整数拆分问题 一、问题描述: 写f(6,4)的求解过程,实际是在求dp[5][5]。 二、问题分析 详情可见博客https://blog.csdn.net/weixin_44279771/article/details/105877374 ????传送门 二、正确答案
  • C++ 整数拆分方法详解

    2020-09-01 22:09:20
    整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧
  • 当前整数的最大值,是由拆分得到的正整数决定的,所以当前状态是由上一个状态推导而来,选用动态规划解决 (1)确定数组及下标含义 dp[i]:表示分拆数字 i ,可以得到的最大乘积 dp[i] (2)确定递推公式 获得 dp...
  • 动态规划: 解决的三种常见问题: 1.最值型问题。 2.计数型问题,求和。 3.存在性问题。 动态规划四步曲: 1.确定状态 ...现在看这个整数拆分的问题: 给定一个正整数 n,将其拆分为至少两个正整数的和
  • class Solution(object): def integerBreak(self, n): """ ... # n为正整数,那么0不是正整数,1是正整数但是不能拆分,所以从2开始 dp = [0 for _ in range(n+1)] for i in range(2, n+1): .
  • 求解整数拆分问题 一、【问题描述】 求将整数无需拆分为最大数为k(称为n的k拆分)的拆分方案个数,要求所有的拆分方案不重复 二、【问题求解】 设n=5,k=5,对应的拆分方案有 ①5=5 ②5=4+1 ③5=3+2 ④5=3+1+1 ⑤5=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,412
精华内容 32,164
关键字:

动态规划整数拆分