题解 | #整数成绩最大化#

#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;
}