美文网首页
[43]整数乘积最大化-招商银行信用卡中心2018秋

[43]整数乘积最大化-招商银行信用卡中心2018秋

作者: jdzhangxin | 来源:发表于2018-11-08 19:51 被阅读12次

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]);
}

牛客题目

相关文章

网友评论

      本文标题:[43]整数乘积最大化-招商银行信用卡中心2018秋

      本文链接:https://www.haomeiwen.com/subject/pftpoftx.html