题解 | #整数成绩最大化#
整数成绩最大化
https://www.nowcoder.com/practice/3e74c3b36fc442db8fdce3057fb1b5b1
#include <iostream>
#include <vector>
using namespace std;
int integerBreak(int n) {
vector<int> dp(n + 1, 0);//dp[i]表示整数i分解为至少两个整数之和时的最大乘积。
for (int i = 2; i <= n; i++) {
int maxProduct = 0;
for (int j = 1; j < i; j++) {
// 分解成 j 和 i-j，然后取最大值,dp[i-j]代表i-j的最大化
maxProduct = max(maxProduct, max(j * (i - j), j * dp[i - j]));
}
dp[i] = maxProduct;
}
return dp[n];
}
int main() {
int n;
cin >> n;
cout << integerBreak(n) << endl;
return 0;
}
