数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学用 C++ 实现整数拆分
假设我们有一个正整数 n，我们需要将它拆分成至少两个正整数之和，并最大化这些整数的乘积。我们需要找到可以得到的最大乘积。因此，如果数字为 10，则答案将为 36，因为 10 = 3 + 3 + 4，3 * 3 * 4 = 36
为了解决这个问题，我们将执行以下步骤 -
定义一个方法 solve()，这将获取 n、数组 dp 和标记
如果 n 为 0，则返回 1
如果 dp[n] 不为 -1，则返回 dp[n]
当标记被设置时，end := n – 1，否则 end := n
ret := 0
对于范围 1 到 end 内的 i
ret := ret 和 i* solve(n – i, dp, false) 的最大值
设置 dp[n] := ret 并返回
从 main 方法中，创建一个大小为 n + 1 的数组 dp，并用 – 1 填充
返回 solve(n, dp)
示例 (C++)
让我们看看以下实施，以便更好地理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int n, vector <int>& dp, bool flag = true){
if(n == 0) return 1;
if(dp[n] != -1) return dp[n];
int end = flag? n - 1: n;
int ret = 0;
for(int i = 1; i <= end; i++){
ret = max(ret, i * solve(n - i, dp, false));
}
return dp[n] = ret;
}
int integerBreak(int n) {
vector <int>dp(n + 1, -1);
return solve(n, dp);
}
};
main(){
Solution ob;
cout << (ob.integerBreak(10));
}输入
10
输出
36
更新于： 2020 年 5 月 2 日
225 次查看
广告