剪绳子，整数拆分

一、题目描述：

二、解题思路：
解法一：贪心算法，尽可能剪多个长度为3的绳子，可证明得长度为3的绳子乘积最大，不留长度为1的绳子，若余1，则将其加到其中一个长度为3的绳子上。

证明：当 n >= 5 时，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下，将绳子剪成一段为 2 或者 3，得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段长度为 3 比长度为 2 得到的乘积更大。

解法二：动态规划，定义动态数组dp[]，先假设绳子的长度为1，则无可剪，dp[1]=1；然后假设长度为2，则可以剪成两个长度1的,dp[2]=1；再假设长度为3，则可以剪成{1,2}和{1,1，1}，dp[3]=2；然后假设长度为4，则{1,3}、{2,2}、{1,1，1,1}，dp[4]=4;再假设长度为5，则{2,3}、{1,4}、{1,2，2}、{1,1，1,1}；对于长度为6的绳子，dp[6] = dp[5](6-5)或者dp[6] = dp[4](6-4)或者dp[6] = dp[3](6-3)或者dp[6] = dp[2](6-2)或者dp[6] = dp[1]*(6-1)，再取最大的就得到dp[6]，以此类推得到dp[n]，即绳子长度为n的最大的乘积。
三、代码：
解法一：

public int integerBreak(int n) {     //贪心算法
		int numthree;
		int remain;
		int result = 0;
		if(n <= 1) {
			return 0;
		} 
		else if(n == 2) {
			return 1;
		}
		else if(n == 3) {
			return 2;
		}
		else {
			numthree = n/3;
			remain = n%3;
			if(remain == 2) {
				result = (int) Math.pow(3, numthree)*2;
			}
			else if(remain == 1) {
				result = (int)Math.pow(3, numthree-1)*(3+1);
			}
			else {
				result = (int)Math.pow(3,numthree);
			}		
			
		}
		return result;
	}

解法二：

public int integerBreak1(int n) {        //动态规划
	    int[] dp = new int[n + 1];
	    dp[1] = 1;
	    for (int i = 2; i <= n; i++)
	        for (int j = 1; j < i; j++)
	            dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
	    return dp[n];
	}