【剑指offer】剪绳子

题目描述

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

分析：

1.如果绳子长度为2，那么只能分两段，长度都为1，返回最大的乘积只能为1。

2.如果绳子长度为3，那么只能分两段或者三段，长度为1、1、1，或者1、2，返回最大长度为2。

3.如果绳子长度大于3，那就要分三个情况：

①能被3整除的，那么就平均分配，每一段长度都为3，就直接返回。

②除以3余1的，如果说前面target/3段绳子全为3，后面剩一个1，那这个乘积肯定不是最大的。那么就有target/3-1段为3的绳子，剩下的一段绳子长度就为4（前面一个3，加上后面的一个1），这个数才应该是最大的。

③除以3余2的，那么就有target/3段绳子长度为3的，剩下一段长度为2的。

代码：

public class Solution { public int cutRope(int target) { if(target == 2){ return 1; } if(target == 3){ return 2; } if(target % 3 == 0){ return (int)Math.pow(3,target/3); } if(target % 3 == 1 ){ return (int)Math.pow(3,(target/3-1))*4; } if(target % 3 == 2){ return (int)Math.pow(3,target/3)*2; } return 0; } }