[刷题防痴呆] 0343 - 整数拆分 (Integer Bre

题目地址

https://leetcode.com/problems/integer-break/description/

题目描述

343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

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

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

思路

• 贪心法. 可以发现要拆分多个数, 并且这些数的绝对值相差小于1最优.
• 因此, 分割成1, 2, 3.
• 如果数大于4, 就继续分割. 每次分走3即可.

关键点

代码

• 语言支持：Java

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
            }
        }
        
        return dp[n];
    }
}

// 贪心
class Solution {
    public int integerBreak(int n) {
        if (n < 4) {
            return n - 1;
        }
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }

        return product * n;
    }
}