代码编织梦想

题目描述:
给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1,m<=n),每段绳子的长度记为k[1],…,k[m]。请问 k [ 1 ] × . . . × k [ m ] k[1]\times...\times k[m] k[1]×...×k[m]可能的最大乘积是多少?例如,当绳子的长度是8时,把它剪成长度分别为2、3、3的三段,得到的最大乘积是18。
示例1:

输入:8
返回值:18
输入描述:输入一个数n,意义见题面。(2 <= n <= 60)
返回值描述:输出答案。

方法一:动态规划
动态规划和递归类似,有如下特点:(1)一般用于求最优解(最大值、最小值);(2)整体问题的最优解依赖于各个子问题的最优解,也就是大问题可以分解成各个子问题;(3)小问题之间还存在相互重叠的更小子问题,对于递归,则会存在重复计算,但是动态规划会把子问题的解缓存起来,从而避免重复求解子问题。(4)从上往下分析问题,从下往上求解问题。

假设把长度为 n n n的绳子剪成若干段,各段长度乘积的最大值为 f ( n ) f(n) f(n)。第一次剪后,绳子变成两段,假设第一段长为 i,则第二段长为(n - i),且 1 < = i < = n − 1 1<=i<=n-1 1<=i<=n1,对于长度为 i 和 (n - i) 的两段绳子可再继续剪下去,这是一个从上往下递归的过程,容易得到:
f ( n ) = m a x ( f ( i ) × f ( n − i ) ) f(n)=max(f(i)\times f(n-i)) f(n)=max(f(i)×f(ni))。这可以通过递归来实现,但是会存在重复计算问题,例如 f ( 7 ) f(7) f(7)分为 f ( 2 ) f(2) f(2) f ( 5 ) f(5) f(5)两个子问题, f ( 5 ) f(5) f(5)又能分为 f ( 2 ) f(2) f(2) f ( 3 ) f(3) f(3)两个子问题,这里 f ( 2 ) f(2) f(2)就会重复计算。为了避免递归的重复计算问题,可以使用动态规划来解决,从下往上求解各个子问题,并把子问题的解缓存起来,通常是缓存在一维数组或二维数组中

为了求解 f ( i ) f(i) f(i),需要求出所有可能的 f ( j ) × f ( i − j ) f(j)\times f(i - j) f(j)×f(ij)的值,并比较得出它们中的最大值,存放在dp数组对应位置。

public class Solution {
    public int cutRope(int target) {
        if (target == 1) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
        return dp[target];
    }
}

时间复杂度:双层for循环, O ( n 2 ) O(n^2) O(n2);空间复杂度:开辟了一个数组空间,用于缓存子问题结果, O ( n ) O(n) O(n)

方法二:贪心算法
剪绳子问题的贪心算法思路

public class Solution {
    public int cutRope(int target) {
        if (target == 1) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int a = target / 3;
        int b = target % 3;
        if (b == 0) return (int) Math.pow(3, a); //pow()方法返回的类型是double,需要强转成int
        if (b == 1) return (int) Math.pow(3, a - 1) * 4;
        return (int) Math.pow(3, a) * 2;
    }
}

时间复杂度: O ( 1 ) O(1) O(1),空间复杂度: O ( 1 ) O(1) O(1)


结束语:如果本篇博客对您有帮助,请点赞、收藏或关注,您的鼓励是博主进步的动力,感谢支持,共同进步。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44072535/article/details/118825641

剑指offer 14.剪绳子 python解法_国宝小十三的博客-爱代码爱编程

题目描述: 给你一根长度为 n 绳子,请把绳子剪成 m 段(m、n 都是整数,2≤n≤58 并且 m≥2)。 每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少? 例如:当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到最大的乘积18。 分析: 书上说的有数学规律:(看注释

剑指offer 14.剪绳子(python)-爱代码爱编程

题目描述 给你一根长度为你的绳子,请把绳子剪成m段(m、n都是整数),n > 1 且 m > 1),每段绳子的长度记为k[0], k[1],…,k[m]。请问k[0] x k[1] x … x k[m]可能的最

《剑指offer》c++版本 14.剪绳子-爱代码爱编程

本题在牛客网剑指offer专项里没看到,原书第二版上有,如题: 这道题是开放的动态规划题,题目中只给了绳子长度,却没定义具体剪多少段,初遇此题,难以下手,看了题解,豁然开朗。设f(n)为常为n的绳子剪成m段之后可得最大值,则存在n-1中减法,得f(n) = MAX(f(i) * f(n-i));初始值f(1),f(2),f(3)都可以计算出来,大于3

剑指offer14 . 剪绳子 p96-爱代码爱编程

剑指offer14 . 剪绳子 P96 题目:给你一根长度为n绳子,请把绳子剪成m段(m、n都是整数,n>1并且m≥1)。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1]…*k[m]可能的最大

剑指 Offer 14. 剪绳子-爱代码爱编程

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1]。请问 k[0]*k[1]...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。 来源:力扣(LeetC

剑指 Offer 14- II. 剪绳子 II-爱代码爱编程

题目 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。 答案需要取模 1e9

剑指offer 14. 剪绳子(动态规划;贪心算法)-爱代码爱编程

2020年12月3日 周四天气晴 【不悲叹过去,不荒废现在,不惧怕未来】 本文目录 1. 题目简介2. 动态规划3. 贪心算法参考文献 1. 题目简介 2. 动态规划 自底向上进行递推,先计算dp[1]、dp[2]、dp[3]… 最终得到dp[n]。 class Solution { public: int cuttingR

剑指offer 14. 剪绳子II(大数求余)-爱代码爱编程

2020年12月4日 周五天气晴 【不悲叹过去,不荒废现在,不惧怕未来】 这道题主体和 剑指offer 14. 剪绳子 一样,唯一不同的就是本题涉及到大数越界情况下的取余问题。 class Solution { public: int cuttingRope(int n) { if (n <= 3) return n - 1;

剑指 Offer 14. 剪绳子java 动态规划与贪心算法-爱代码爱编程

题目描述 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子 的长度记为 k[0],k[1]...k[m-1] 。请问 k[0] * k[1] *...*k[m-1] 可能的最大乘积是多少? 例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

剑指Offer 14.剪绳子-爱代码爱编程

题目: 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。 输入: 2 输出

[菜鸟训练]剑指 Offer 14. 剪绳子-爱代码爱编程

题目描述: 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。 示例 1: 输入: 2

剑指offer 14. 剪绳子-爱代码爱编程

剑指offer 14.剪绳子 1、贪心算法 数学推导:得出尽可能将绳子以长度3切分,乘积最大LeetCode推导过程 当n整除3后绳长为0时,返回3的n/3次方; 当n整除3后绳长为1时,应将前一个3与剩余的1拆分成2和2,返回3的n/3-1次方 * 22; 当n整除3后绳长为2时,返回3的n/3次方2 public: int cuttingR

绳索运动的C语言编程,【leetcode C语言实现】剑指 Offer 14. 剪绳子-爱代码爱编程

题目描述 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。 示例 1:

剑指 Offer 14.剪绳子(动态规划、数学分析)-爱代码爱编程

一、题目内容          二、题目分析         这道题目讲道理,我看到的第一眼就是动态规划,但是后来提交之后,发现还有大佬考虑用数学分析得出精简解法,在这里我也会一 一阐述。         对于动态规划而言,按照老套路,首先定义dp数组,含义明了,定义长度为n+1的dp数组,其中dp[i]代表长度为i的绳子的最大乘积。