整数拆分

Leetcode Link: 343. 整数拆分 - 力扣（LeetCode） 剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode）

题目

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

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

解法一

思路：

数学中针对该问题有相关的推论和证明(可以看这里)，总结来说，我们的拆分规则是

1. 最优：3。把数字尽可能地拆分成因子 3，余数可能为 0，1，2 三种情况
2. 次优：2。若余数为 2，则保留，不再拆分成 1+1
3. 最差：1。若余数为1，则应该把一个3*1拆成2*2，因为3*1<2*2

题解： 自己的写法

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2: return 1
        if n == 3: return 2
 
        n3 = n // 3
        mod = n % 3
        if mod == 2:
            return 3**n3*2
        if mod == 1:
            return 3**(n3-1)*2*2
        if mod == 0:
            return 3**n3

网友写法

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3: return n - 1  # 输入为2，3的时候结果好牛逼
        a, b = n // 3, n % 3
        if b == 0: return int(math.pow(3, a))
        if b == 1: return int(math.pow(3, a - 1) * 4)
        return int(math.pow(3, a) * 2)

解法二

从暴力递归到动态规划

1. 暴力递归

思考：假设任何一个数字拆分后得到的最大乘积为 f(n)。对于任意一个数，其实拆分成多少个我们不能确定。假设拆分成两个: i 和 n-i，那么对于这个拆分，结果一定为 res=max(res, f(i)*f(n-i))，即考虑我拆，还是不拆。

我们需要做的是遍历 i (从 2 到 n)，找出这个最大的拆分乘积。 具体最终拆成多少个，要看其拆出来的两个 f(i)*f(n-i) 拆出来多少个，这样就不限制拆成 2 个

Tips

1. 肯定不能拆成 1 和 n-1，因为 $1\times (n-1)<n$
2. 考虑对称的情况，譬如对于 n=5 来说，拆成 2*3 和 3*2 是一样的
3. 由于一定要拆分，下面的程序中并不知道怎么加入”一定”的逻辑，所以实际上的逻辑是如果拆了比不拆小，就不拆，因此需要把特例放进去（2 和 3 是特例，但是不是 base case, base case 和特例的值是不一样的，原因是base case是不能拆分的，但是特例是必需拆分的）

class Solution:
	'''会超时，可以自己尝试几个不超时的例子，都是对的'''
    def integerBreak(self, n: int) -> int:
        def recur(num):
            if num == 1 or num==2:
                return num
            ans = num
            for i in range(2, (num+1)//2+1): # Tips 1和2
                ans = max(ans, recur(num-i)*recur(i))
            return ans
 
        # 两个特例：拆了比不拆小
        if n == 2: return 1
        if n == 3: return 2
        return recur(n)

2. 添加备忘录（记忆化搜索），自顶向下

在1)的基础上，剪枝，添加备忘录dp，下标表示当前值的最大拆分乘积(即dp[i])

class Solution:
	'''可以在要求时间内跑通了'''
    def integerBreak(self, n: int) -> int:
        dp = [None] * (n + 1)  # 浪费了 dp[0]，为了逻辑一致
        dp[1] = 1  # 两个 base case，区别于特例
        dp[2] = 2
        def recur(num):
            if dp[num] != None:
                return dp[num]
            
            ans = num
            for i in range(2, (num+1)//2+1):
                ans = max(ans, recur(num-i)*recur(i))
            dp[num] = ans
            return ans
        
        if n == 2: return 1
        if n == 3: return 2
        return recur(n)

可以看到，这里已经没有关于base case 的判断了，而是将base case 放在了 dp 中

3. 自下向上，纯正的动态规划

显然，对于每一个数字 n，是和之前所有的状态都有关，而不是和固定个数个状态有关（区别于斐波那契数列和爬楼梯）。因此需要遍历所有个状态。根据 2) 可以写出自下向上的纯动归解法为

class Solution:
    def integerBreak(self, n: int) -> int:
 
        if n == 2: return 1
        if n == 3: return 2
        
		# **这里 dp 必需要赋值成自身，否则结果不对，因为 dp 中的值有可能不拆，而下面的写法表示必需拆。**
		# 显然，如果改成for i in range(0, (num+1)//2+1)就可以了
		# 或者可以赋值成[0]*(n+1)后打印dp[3]看看结果就理解了
        dp = [x for x in range(n+1)] # 浪费了 dp[0]
        dp[1] = 1
        dp[2] = 2
        for num in range(3, n+1):  # 往上走
            for i in range(2, (num+1)//2+1): # 拆后找当前num数的最大拆分乘积
                dp[num] = max(dp[num], dp[i]*dp[num-i])
       
        return dp[n]

傻子情况，假设拆成 i, i-k

很有可能某一个就不拆了，所以情况都列全了，很多细节就不用注意了，因为思考上面的细节很绕。

1. i*i-k
2. dp[i]*(i-k)
3. i*dp[i-k]
4. dp[i]*dp[i-k]

4. 代码随想录改进版

在上面的方法中，我比较的是max(res, dp[i]*dp[num-i])来求dp的，这样的缺点是需要考虑特例。

在随想录中，他的比较是 max(dp[i], max(j * (i - j), j * dp[i - j])，这样是不用比较特例的。

同时，他的dp[2]的值和我的也不同，这样看来，我的方法在处理特例和base case的时候，会产生逻辑不一致性。

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1  #### --- 区别 1
        for num in range(3, n + 1):
            for i in range(1, num - 1): #### -- 区别 2
                dp[num] = max(dp[num], i * (num - i), i * dp[num - i])
        return dp[n]

假设对正整数 num 拆分出的第一个正整数是 i（1 ⇐i < num），则有以下两种方案：

1. 将 num 拆分成 i 和 num−i 的和，且 num−i 不再拆分成多个正整数，此时的乘积是 i * (num-i) （这里要求它必需遍历完所有的 i,而不能像我一样从中间结束，因为这里固定的是一个不拆）
2. 将 num 拆分成 i 和 num−i 的和，且 num−i 继续拆分成多个正整数，此时的乘积是 i * dp[num-i]

启发和联系

牛逼的课程，看完直接自己写 左程云 ： 看P2-P6就够了