343. Integer Break -- 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
代码语言：javascript复制输入: 2
输出: 1
解释: 2 = 1 1, 1 × 1 = 1。示例 2:
代码语言：javascript复制输入: 10
输出: 36
解释: 10 = 3 3 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。
分析
分割4获得最大乘积拆分为：
1 ？分割3获得最大乘积 --》 1 ？ 分割2 ；2 ？分割1 -- 》分割1
2 ？分割2获得最大乘积
3 ？分割1获得最大乘积
最优子结构：通过求子问题的最优解，可以获得原问题的最优解
一、递归
代码语言：javascript复制// @lc code=start
class Solution {
private:
int max3( int a, int b, int c ) {
return( a, max(b, c) );
}
// 将n进行分割（至少分割两部分），可以获得的最大乘积
int breakInteger(int n) {
if( n == 1 )
return 1;
int res = -1;
for( int i = 1; i <= n-1; i )
// i (n - i)
res = max3( res, i * (n-i), i * breakInteger(n-i));
return res;
}
public:
int integerBreak(int n) {
return breakInteger(n);
}
};
// @lc code=end二、记忆化搜索
代码语言：javascript复制// @lc code=start
class Solution {
private:
vector<int> memo;
int max3( int a, int b, int c ) {
return( a, max(b, c) );
}
// 将n进行分割（至少分割两部分），可以获得的最大乘积
int breakInteger(int n) {
if( n == 1 )
return 1;
if ( memo[n] != -1)
return memo[n];
int res = -1;
for( int i = 1; i <= n - 1; i )
// i (n - i)
res = max3( res, i * (n-i), i * breakInteger(n-i) );
memo[n] = res;
return res;
}
public:
int integerBreak(int n) {
assert( n >= 1);
memo.clear();
for (int i = 0; i < n 1; i )
memo.push_back(-1);
return breakInteger(n);
}
};
// @lc code=end// @lc code=start
class Solution {
private:
vector<int> memo;
int max3(int a, int b, int c) {
return max( a, max( b, c) );
}
int breakInteger(int n) {
if ( n == 1 )
return 1;
if( memo[n] != -1 )
return memo[n];
int res = -1;
for( int i = 1; i <= n - 1; i )
res = max3( res, i*(n-i), i * breakInteger(n - i) );
memo[n] = res;
return res;
}
public:
int integerBreak(int n) {
assert( n >= 1) ;
memo = vector<int>(n 1, -1);
return breakInteger(n);
}
};
// @lc code=end 自底向上
代码语言：javascript复制// @lc code=start
class Solution {
private:
int max3(int a, int b, int c) {
return max( a, max( b, c) );
}
public:
int integerBreak(int n) {
assert( n >= 2) ;
// memo[i]表示将数字i分割（至少分割成两部分）后得到的最大乘积
vector<int> memo(n 1, -1);
memo[1] = 1;
for (int i = 2; i <= n; i )
// 求解memo[i]
for(int j = 1; j <= i - 1; j )
// j (i-j)
memo[i] = max3( memo[i], j*(i-j), j * memo[i-j]);
return memo[n];
}
};
// @lc code=end 
