可视化图解算法78：整数拆分

1.题目

描述

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n =2

输出:1

解释:2=1+1,1 × 1=1。

示例 2:

输入: n =10

输出:36

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

提示:

• 2 <= n <= 58

2. 题解思路

本题如果不是强调用动态规划，很难想到用动态规划来解决。对于一个整数的拆分，也有技巧：对于一个数，可以拆分为2个数的乘机，也可以拆分成多个数的乘机。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3.编码实现

核心代码如下：

func integerBreak(n int) int {
    //1.定义状态.   i：给定的正整数;   dp[i]：对i进行拆分，最大的乘机
    dp := make([]int, n+1)
    //2.初始化边界条件：
    dp[0] = 0 //0只能拆分为：0与0,相乘结果为0
    dp[1] = 0 //1只能拆分为：1与0,相乘结果为0
    dp[2] = 1 //2可以拆分为：1与1,最大相乘结果为1
    //3.确定递推公式：
    for i := 3; i <= n; i++ {
        for j := 1; j < i; j++ {
            //for j := 1; j <= i/2; j++ {
            dp[i] = max(j*(i-j), j*(dp[i-j]), dp[i]) //对于每一个i，有多次的拆分，因此需要对每次的dp[i]取最大值
            fmt.Printf("%d\t", dp[i])
        }
    }
    fmt.Println("\n", dp)
    // 4.输出结果
    return dp[n]
}
func max(a, b, c int) int {
    var maxValue int
    if b <= a && c <= a {
        maxValue = a
    } else if a <= b && c <= b {
        maxValue = b
    } else {
        maxValue = c
    }
    return maxValue
}

具体完整代码你可以参考下面视频的详细讲解。

• Python编码：B站@好易学数据结构
• Java编码：B站@好易学数据结构
• Golang编码：B站@好易学数据结构

4.总结

本题想对来说还是比较难，难点是想到用动态规划解决，并且对一个整数拆分的情况进行细分。对i进行拆分包括2种情况：

• 拆分为2个数：j x（i-j）；
• 拆分为3个数或者更多，即固定j，对 i-j 进一步拆分：j x dp[i-j]；其中，j为变量，取值为：[1:i-1]

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

✅ 链表

✅ 二叉树

✅ 二分查找、排序

✅ 堆、栈、队列

✅ 回溯算法

✅ 哈希算法

✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：B站@好易学数据结构
• Java编码实现：B站@好易学数据结构
• Golang编码实现：B站@好易学数据结构

对于LeetCode数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：三更灯火五更鸡，正是男儿读书时。