343. 整数拆分

leetcode 343. 整数拆分

题目：343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明:

你可以假设 n 不小于 2 且不大于 58。

方法一：动态规划

思路：动态规划，状态转移方程为：dp[i] = max(dp[i], j * max(dp[i - j], i - j));（dp[i]表示表示拆分i的乘积最大值），求dp[i]将i拆分为j和i - j两个部分求乘积。

运行数据：执行用时：1 ms，内存消耗：35.3 MB

复杂度分析：

• 时间复杂度：O(n^2)，两层循环的时间复杂度。
• 空间复杂度：O(n)，dp数组所消耗的空间。

1
2
3
4
5
6
7
8
9
10
11

// LeetCode指定调用方法 
public int integerBreak(int n) {
		
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i / 2; j++) {
            dp[i] = Math.max(dp[i], j * Math.max(dp[i - j], i - j));
        }
    }
    return dp[n];
}

方法二：优化动态规划

思路：优化动态规划，状态转移方程为：dp[i] = max(2 * (i - 2), 2 * dp[i - 2],3 * (i - 3), 3 * dp[i - 3]);（dp[i]表示表示拆分i的乘积最大值），根据题意找规律，求dp[i]只需要判断将i拆分为2和i - 2以及3和i - 3这两中分拆分情况的最大值即可。

运行数据：执行用时：0 ms，内存消耗：35.3 MB

复杂度分析：

• 时间复杂度：O(n)，只需循环n - 3次即可。
• 空间复杂度：O(n)，dp数组所消耗的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13

// LeetCode指定调用方法 
public int integerBreak(int n) {
		
    if (n < 4) {
        return n - 1;
    }
    int[] dp = new int[n + 1];
    dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
    }
    return dp[n];
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！