最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

经典面试题27_剪绳子解法思路

XAMPP相关 admin 267浏览 0评论

来源:LeetCode

难度:中等

描述:

给你一根长度为 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
输出:1
解释:2 = 1 + 1, 1 × 1 = 1

示例2:

输入:10
输出:36
解释:10 = 3 + 3 + 4, 3 × 3 × 4 = 36

分析:

题意是给咱们一个长度为n的绳子,让咱们任意剪成m段,并求出剪出的m段绳子长度乘积最大是多少

一看到这个题下意识想到的是数学中的知识:要使乘积最大,则要使每一段的差是最小的。

由于剪成一段相当于没剪,所以咱们从 m = 2 开始剪,每次只将其尽量均分,如果没法直接均分,则将剩下的长度挨个均分给其他各段一个单位,最后计算每次结果乘积,并保留乘积最大值即可

还有一种思路是动态规划,这其实也是一个全局最优解的问题,长度为n的绳子剪掉后的最大乘积,可以从前面比n小的绳子转移而来。所以用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积,也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积。两种解法具体步骤如下:

 

解题

方法一:数学法

思路:

如分析,从 m = 2 开始,每次将绳子长度n尽量均分,如果没法直接均分,则将剩下的分给其他各段一个单位。然后计算每种均分下的乘积,并保留最大值

 

代码:

 1public int cuttingRope(int n) {
 2    int max = 1;
 3    // i 表示切分的段数
 4    for (int i = 2; i < n; i++) {
 5        // 平均切分为i段后,每段的长度为a
 6        int a = n / i;
 7        // 平均切分后剩余的不足一段的绳子长度为b
 8        // 将这些不足的分给其他段一个单位
 9        int b = n % i;
10        //a为平均长度、b为多出来的长度,将b平均分给每一段,每段+1
11        //则有长度为a 的绳子 i-b段,长度为 a + 1的绳子 b段,求乘积
12        int temp = (int) (Math.pow(a, (i - b)) * Math.pow(a + 1, b));
13        max = Math.max(max, temp);
14    }
15    return max;
16}

时间复杂度:O(n)

空间复杂度:O(1) 

 

方法二:动态规划

思路:

用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积,也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积

长度从2开始剪(剪长度为1的绳子没有意义),假设当前绳子程度为i,第一次剪了 j ,那么剩余长度为 i – j。对于剩下的绳子 i – j 有剪和不剪两种情况:

      • 不剪,那么得到的乘积为j * (i – j)
      • 剪,那么得到的乘积为 j * dp[i – j],其中dp[i – j] 表示长度为 i- j的绳子剪m段能得到的最大乘积

所以动态规划方程为 dp[i] = max(j * (i – j), j * dp[i – j])

 

代码:

 1public int cuttingRope1(int n) {
 2    int[] dp = new int[n + 1];
 3    dp[2] = 1;
 4    // dp[2]为初始值,i从3开始
 5    for (int i = 3; i <= n; i++) {
 6        //剪的长度j从2开始
 7        for (int j = 2; j < i; j++) {
 8            //dp[i] = max(j * (i - j), j * dp[i - j]) 
 9            int temp = Math.max(j * (i - j), j * dp[i - j]);
10            //dp[i]保存最大值
11            dp[i] = Math.max(dp[i], temp);
12        }
13    }
14    return dp[n];
15}

时间复杂度:O(n * n)

空间复杂度:O(n) 

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 经典面试题27_剪绳子解法思路

您必须 登录 才能发表评论!