剪绳子

(color{blue}{**题目描述**})

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

(color{blue}{**输入描述**})

输入一个数n，意义见题面。（2 <= n <= 60）

(color{blue}{**输出描述**})

输出答案。
示例1
输入
复制
8
输出
复制
18

题解思路：

 先举几个例子，可以看出规律来。
 4 ： 2*2
 5 ： 2*3
 6 ： 3*3
 7 ： 2*2*3 或者4*3
 8 ： 2*3*3
 9 ： 3*3*3
10：2*2*3*3 或者4*3*3
11：2*3*3*3
12：3*3*3*3
13：2*2*3*3*3 或者4*3*3*3

最终结果就是：(2^x*3^y)，只需要确定x和y就可以了
如果有3尽量先取出3，之后再取2，但是注意(4=2*2)不是(4=3*1)
也就是说取3之后最后的临界是while(n>4)而不是while(n>0)

class Solution {
public:
    int cutRope(int n) {
int three=0,two=0;
if(n==2){
return 1;	
}else if(n==3){
	return 2;
}else{
	int t;
	if(n%3==0){//例如：9=3*3*3
		t=0;
	}else{
		t=4;
	}
	while(n>t){
		n-=3;
		three++;
	}
	while(n>0){
		n-=2;
		two++;
	}
	return pow(2,two)*pow(3,three); 
}
    }
};

class Solution {
    public int cuttingRope(int n) {
    if(n==2) return 1;
    if(n==3) return 2;
    int []dp = new int[100];
  //长度剪到1,2,3不用剪断
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
   
    for(int i=4;i<=n;i++){
        for(int j=1;j<4;j++){
   dp[i] = Math.max(dp[i],dp[i-j]*j);
        }
        
    }
    return dp[n];
    }
}