1.题目描述
给出一个整数n,将n分解为至少两个整数之和,使得这些整数的乘积最大化,输出能够获得的最大的乘积。
例如:
2=1+1,输出1;
10=3+3+4,输出36。
- 输入描述:
输入为1个整数 - 输出描述:
输出为1个整数 - 输入示例:
10
- 输出示例:
36
2.题目解析
完全背包问题,一个整数n
分解结成多个整数之和,有如下几种情况。
3.参考答案
- 递归
#include <bits/stdc++.h>
using namespace std;
int solve(int i,int sum){
if(i == 0) return 1; // 数字边界
if(sum == 0) return 1; // 正好满足条件
if(sum < 0) return -1; // 不满足条件
return max(solve(i,sum-i)*i, // 选择当前数字i
solve(i-1,sum)); // 不选择当前数字i
}
int main(){
int n=0;
scanf("%d",&n);
printf("%d",solve(n,n));
}
- 自顶而下(备忘录)
#include <bits/stdc++.h>
using namespace std;
int solve(int i,int sum,vector<vector<int> >& dp){
if(i == 0) return 1; // 数字边界
if(sum == 0) return 1; // 正好满足条件
if(sum < 0) return -1; // 不满足条件
if(-1 != dp[i][sum]) return dp[i][sum];
return dp[i][sum] = max(solve(i,sum-i,dp)*i, // 选择当前数字i
solve(i-1,sum,dp)); // 不选择当前数字i
}
int main(){
int n=0;
scanf("%d",&n);
vector<vector<int> > dp(n+1,vector<int>(n+1,-1));
printf("%d",solve(n,n,dp));
}
- 自底而上(递推)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=0;
scanf("%d",&n);
vector<vector<int> > dp(n+1,vector<int>(n+1,1));
for(int i=1;i!=n+1;++i){
for(int sum=1;sum!=n+1;++sum){
if(sum >= i){
dp[i][sum] = max(dp[i][sum-i]*i,dp[i-1][sum]);
} else {
dp[i][sum] = dp[i-1][sum];
}
}
}
printf("%d",dp[n][n]);
}
- 滚动数组优化
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=0;
scanf("%d",&n);
int dp[n+1];
fill_n(dp,n+1,1);
for(int i=1;i!=n+1;++i){
for(int sum=i;sum!=n+1;++sum){
dp[sum] = max(dp[sum-i]*i,dp[sum]);
}
}
printf("%d\n",dp[n]);
}
网友评论