leecode 解题总结：343. Integer Break

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
/*
问题:
Given a positive integer n, break it into the sum of at least two positive integers 
and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

分析:将一个正整数分解为至少两个整数，然后使得分解后整数的乘积最大。
看题目的样子应该是动态规矩话或者回溯。
关键如何使得乘积最大：我们知道最多一个整数n分解成:n个整数，最少分解为两个整数:
因为分解为两个最接近的整数的时候乘积最大，所以
分解为两个整数的时候：n为偶数:(n/2)^2， n为奇数: (n+1)/2,n/2
分解为三个整数的时候也是三个数越接近越大
比如:11，分解为2个是:5 * 6 = 30 ,分解为3个是: 3 * 4^2 = 48
分解为4个是: 2*3^3=2 * 27 = 54, 分解为5个是: 2^4 * 3 = 16 *3 = 48
分解为6个是:1 * 2^(5) = 32

输入:
2
10
11
输出:
1
36
54

关键:
1 使得分解的整数最接近的时候最大，因此，尝试将数n
分解成2个,3个,...n个，记录分解过程中的最大值即可

2 当成动态规划来求，设dp[i]表示数i的最大分解后的乘积，
则对于数n的最大乘积，要么是i*(n-i)，要么是i乘以数n-1分解后
的最大乘积
dp[i]=max(j * dp[i-j] , j * (i-j))，i属于3到n,因为要生成dp[n],前面的必须要先计算
出来,j属于1到i-1
边界dp[1]=1,dp[2]=1,所求目标dp[n]

*/

class Solution {
public:
    int integerBreak2(int n) {
        long long maxValue = INT_MIN;
		//尝试把数分解成2个，3个,...,n个,n要取到，否则2无法计算
		for(int i = 2 ; i <= n ; i++)
		{
			int avg = n / i;
			int remainder = n - avg * i;
			long long result = (int) ( pow(avg , i - remainder) * pow(avg + 1 , remainder) );
			maxValue = max(result , maxValue);
		}
		return (int)maxValue;
    }

	//dp动态规划方程,
    int integerBreak(int n) {
        vector<int> dp(n + 1, 1);
		dp.at(2) = 1;
		for(int i = 3; i <= n; i++)
		{
			for(int j = 1 ; j < i ; j++)
			{
				int value = max( j * dp[i-j] , j *(i - j));
				dp[i] = max(value , dp[i]);
			}
		}
		return dp[n];
    }
};

void process()
{
	 int num;
	 Solution solution;
	 int result;
	 while(cin >> num )
	 {
		 result = solution.integerBreak(num);
		 cout << result << endl;
	 }
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}