算法:剪绳子

剪绳子
1. 分析
2. 代码

剪绳子

给你一根长度为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）

示例:

输入

输出

分析

① 动态规划

分析题目可知:

当长度小于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]}

② 贪心

代码

① 动态规划

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];
    }
}

② 贪心

尽可能的拆分出3;

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

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

下面是f(x)的导数：

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

f(x)的函数图像

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

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

上式中除法向下取整

当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);
    }
}