剪绳子

题目描述

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

输出描述:

输出答案。

示例1

输入

8

输出

18

我看到题目的第一想法就是递归，首先考虑一下特殊情况，当n=1、2、3时，最大乘积分别为1,1,2
n=4也是特殊情况，可以分成2*2，最大乘积为4。n>4时，将绳子分割一定大于本身长度，简单证明一下:

$2*(n-2) - n = n-4 > 0 (n>4)$

因此n>4之后都需要将绳子分成若干个2和3的长度，只需要比较是2 * cutRope(n-2)大，还是3 * cutRope(n-3)大。

但要注意一点，我们在绳子长度大于3时，要阻止程序对绳子长度为2、3进行进一步分割，使用Math.max就可以让绳子在长度为2、3时停止分割。

import java.lang.Math;
public class Solution {
    public int cutRope(int target) {
        if (target < 4) {
            return target - 1;
        }
        return Math.max(2*Math.max(target-2,cutRope(target-2)),
                                  3*Math.max(target-3,cutRope(target-3)));
    }
}