一、问题描述

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

示例 1:

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

示例 2:

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

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

二、方案一：动态规划

1、思路

动态规划的核心思想是，将问题分解为更小的子问题，并存储这些子问题的解，以避免重复计算。对于整数拆分问题，我们可以定义一个数组 dp，其中 dp[i] 表示将整数 i 拆分后得到的最大乘积。

• 初始化 dp[0] = 0 和 dp[1] = 0，因为 0 和 1 不能被拆分。
• 对于每个 i 从 2 到 n，我们需要考虑所有可能的拆分方式，并更新 dp[i]。

2、代码实现

func integerBreak(n int) int {
    // 初始化 dp 数组
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        for j := 1; j < i; j++ {
            // 对于每个 i，考虑所有可能的拆分方式
            dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]))
        }
    }
    return dp[n]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n^2)，我们需要计算 dp 数组中的每个元素，每个元素的计算都需要 O(n) 的时间。
• 空间复杂度：O(n)，我们需要一个长度为 n+1 的数组来存储 dp 的值。

三、方案二：贪心算法

1、思路

贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。 对于整数拆分问题，我们可以观察到，当 n 大于等于 4 时，拆分成多个 3 的和会得到更大的乘积。因此，我们可以尽可能多地拆分出 3，直到剩余的数为 2 或 3。

2、代码实现

func integerBreak(n int) int {
    if n <= 3 {
        return n - 1
    }
    // 计算可以拆分出多少个 3
    a, b := n/3, n%3
    if b == 0 {
        // 如果剩余为 0，则直接返回 3 的幂
        return int(math.Pow(3, float64(a)))
    } else if b == 1 {
        // 如果剩余为 1，则返回 3 的幂乘以 4
        return int(math.Pow(3, float64(a-1))) * 4
    } else {
        // 如果剩余为 2，则返回 3 的幂乘以 2
        return int(math.Pow(3, float64(a))) * 2
    }
}

3、复杂度分析

• 时间复杂度：O(1)，我们只需要计算几个简单的数学表达式。
• 空间复杂度：O(1)，我们不需要额外的空间来存储中间结果。

四、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(n^2)	O(n)	动态规划，适用于所有情况
方案二	O(1)	O(1)	贪心算法，仅适用于整数拆分问题

对于整数拆分问题，贪心算法提供了一个简单且效率高的解决方案。然而，动态规划方法更加通用，可以适用于更广泛的问题。在实际应用中，选择哪种算法取决于具体问题的需求和背景。