343-整数分解

LeetCode 343. Integer Break

LeetCode-343

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

method

整数拆解，要求拆解出来的数的乘积最大

• dp[i]表示整数i的拆解最大乘积
• 对于一个数i，可以从1开始拆解，直到i-1
• 算一下直接相乘的j * (i-j)大，还是需要继续分解j * dp[i-j]

状态转移方程：dp[i] = max(j * (i-j), j * dp[i-j])
因为在j遍历的过程中，需要更新dp[i]的最大值，所以还需要一个max

int integerBreak(int n) {
    vector<int> dp(n + 1);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}