leetcode代码记录（整数拆分

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. 我的代码：

class Solution:
    def integerBreak(self, n: int) -> int:
        # dp数组定义
        dp = [0] * (n + 1)

        # dp数组初始化
        dp[0] = 0
        dp[1] = 0
        dp[2] = 1

        # 遍历
        for i in range(3, n + 1):
            for j in range(1, i // 2 + 1):
                dp[i] = max(j * dp[i - j], dp[i], j * (i - j))

        return dp[n]

动态规划最重要最需要理清楚的点：

1. dp数组及其下标的含义
2. 递推公式
3. dp数组初始化
4. 遍历顺序

这里，通过推理得到：

1. dp数组的下标代表的是整数值，dp数组的值代表的是这个整数拆分后乘积的最大值
2. 递推公式j * dp[i - j]表示拆分的情况，j * (i - j)表示不拆分的情况，递推的每一步都需要把拆解方法都试一遍，第一个数字拆出来的范围就是1到i // 2，因为比i // 2大的话，i - j这个被拆的数就一定无法满足数字尽可能相同，要拆当然是拆大的。还要和之前拆的dp[i]比较一下，所以综合下来，递推公式就是：dp[i] = max(j * dp[i - j], dp[i], j * (i - j))
3. dp数组的初始化：dp[0]肯定没有意义，dp[1]也没有意义，dp[2]等于1 * 1 = 1，因此给dp[0]和dp[1]都赋值为0，防止继续递推下去，如果递推下去就会0乘以任何数都是0
4. 遍历顺序就是从3到n即可，最后输出的就是dp[n]