给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
力扣(LeetCode)第343题
题目分析
①.暴力枚举
一个正整数 n 拆分成两个数,可用枚举所有情况,1+n-1、2+n-2、…、i+(n-i) 、(n-1)+1,比较每种情况相乘的结果即最终的值;对于每种情况:i+(n-i),比较 (n-i) 和 (n-i) 继续拆分得到值的大小来确定是否拆分。
②.map 优化
对于每种情况 i+(n-i) 求解的过程中,都会对 n-i … 1 的所有整数的拆分进行求解,因此递归过程存在重复计算,可以用 map 保存过程中的值,即记忆化搜索。
代码示例
class Solution {
public:
unordered_map<int,int> mp;//建立备忘录,用于记忆化搜索
int integerBreak(int n) {
mp[1] = 1;//初始化
mp[2] = 1;
return dp(n);
}
int dp(int n)
{
int res = 0;
if( mp.find(n) != mp.end())
{
return mp[n];//备忘录中存在,直接返回结果
}
for(int i = 1;i < n;i++)//枚举所有情况
{
int temp = max(i*(n-i),i*dp(n-i));//判断是否继续拆分
res = max(res,temp);
}
mp[n] = res;
return res;
}
};