本文共 1125 字，大约阅读时间需要 3 分钟。

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

1、回溯法（对于每一种整数分解形式，计算乘积，结果超时） 

int product = 1; // 乘积	int MaxProduct = 1; // 最大乘积	public int integerBreak(int n)	{		if (n == 2)			return 1;				resolveNum(n, product);		return MaxProduct;	}		/**	 * 整数分解,计算每一种分解形式的乘积(回溯法)	 * @param n 被减数	 * @param sub 减数	 */	void resolveNum(int n, int sub)	{		if (n <= sub) // 一次整数分解完成		{			MaxProduct = Math.max(product*n, MaxProduct);		}		else		{			for (int i=2; i
   
     0) { 					product *= i; // 本次乘积					resolveNum(n-i, i);					product /= i; // 恢复				}			}		}	}
   

 2、记忆化搜索

int[] dp  = null; // 备忘录	public int integerBreak(int n)	{		if (n == 2)			return 1;				dp = new int[n+1];		return breakInteger(n);	}	int breakInteger(int n)	{		int maxProduct = 0;				if (n == 1)			return 1;				// 如果计算过		if (dp[n] != 0)			return dp[n];				for (int i=1; i<=n; i++)		{			// 分为两种情况，一种是只分成两个部分i和n-i，另一种i和递归breakInteger(n-i)			maxProduct = max(maxProduct, i*breakInteger(n-i), i*(n-i));		}		dp[n] = maxProduct;				return dp[n];	}

转载地址：http://xcpoi.baihongyu.com/