資料結構
網路
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 次檢視
廣告