整数分解使得积最大

题目：

给一个数n，你可以将这个数拆成任意个整数之和。找出在所有的拆分方式中，拆出来的所有的数的积的最大值（也包括只拆成一个数，如2拆成2最大）。

如 n = 6, 可以拆成
3 * 3 = 9 2 * 4 = 8
2 * 2 * 2 = 8 1 * 1 * 4 = 4
1 * 1 * 2 * 2 = 4 ...
最大值为9。

分析：

比较容易想到的是使用动态规划来解该题。首先找出状态方程，可以设f(n)为n拆分后积最大的值，则f(n)=max{i*f(n-i)}, i=1,2...n-1。其中f(1)=1, f(2)=2。使用递归效率上可能会有点问题，不过也很容易改成非递归。

动态规划法代码：

//递归法
int f(int N) {
	if (N == 1 || N == 2)
		return N;
	int max = N;
	for (int i = 1; i < N; i++) {
		int tmp = i * f(N - i);
		if (tmp > max)
			max = tmp;
	}
	return max;
}

如果题目改成分解的数字不能有重复，比如6不能分解为3+3，则可以参见http://blog.csdn.net/jqmczx/article/details/6400723的分析。