仓库源文站点原文


title: '算法:剪绳子' cover: https://img.paulzzh.com/touhou/random?69 categories: 算法题目 date: 1996-07-27 08:00:00 tags: [算法题目, 动态规划, 贪心]

toc: true

<br/>

<!--more-->

剪绳子

剪绳子

给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],...,k[m]。

请问k[0]xk[1]x...xk[m]可能的最大乘积是多少?

例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

输入描述: 输入一个数n,意义见题面。(2 <= n <= 60)

示例:

输入

8

输出

18

分析

① 动态规划

分析题目可知:

当长度小于2时, 无法切分, 此时返回0;

当长度为2时, 结果为1;

当长度为3时, 结果为2;

当长度等于4时, 结果为2x2;

当长度为5时, 结果为3x2;

……

使用动态规划, 则dp[i]表示长度为i时的最大乘积

可知:

dp[1] = 1;

dp[2] = 2;

dp[3] = 3;

原因是: 在n<=4时, dp中存放的应当是可以选择一刀不切的最大值

当n大于4时,我们尽可能多的剪长度为3的绳子;

当剩下的绳子长度为4时,把绳子剪成两段长度为2的绳子。

dp[i] = max{dp[k] x dp[i - k]}

<br/>

② 贪心


代码

① 动态规划

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

<br/>

② 贪心

尽可能的拆分出3;

给出一个为什么选择3的数学解释。

问题类似于定周长求最大面积的问题(例如给定四边形周长,求最大面积),当k[0]==k[1]==,==k[m]时乘积最大,设k[0]=x,那么n=x*m,乘积可以用下式表示f(x)=(x)^(n/x)

下面是f(x)的导数:

img

乘积函数在n/m=e的时候,取得最大值,可知,当x∈(0,e)时f(x)单调递增,当x>e时,单调递减,因此,在x=e时取得最大值,e≈2.718,是自然对数。 从函数图像上也可以看出这一点

f(x)的函数图像

img

又因为x的取值只能为整数,且f(3)>f(2),所以,当n>3时,将n尽可能地分割为3的和时,乘积最大。

当n>3时,有三种情况,即n%3==0, n%3==1, n%3==2,如下所示

img

上式中除法向下取整

当n≤3时,只有

当n==2时f(x)=1;

当n==3时f(x)=2;

public class Solution {
    public static int cutRope(int n) {
        if (n == 2) return 1;
        else if (n == 3) return 2;

        if (n % 3 == 0) return (int) Math.pow(3, n / 3);
        else if (n % 3 == 1) return 4 * (int) Math.pow(3, n / 3 - 1);
        else return 2 * (int) Math.pow(3, n / 3);
    }
}