leetcode 343

题目来自leetcode 343 integer break

对于本题，尝试了两种方法，第一种方法比较直接，直接针对题目中的问题求解，但效率较低，第二种方法对问题进行了数学分析，效率较高：

一，直接求解

1、算法分析

对于该题来讲，首先我们根据题目所述我们需要对一个整数进行加法的拆解，然后最大化这个乘积。由于没有确定要将原分成几部分，所以很难解决，但我们可以把它当作一个二分的问题，这样我们就可以用迭代的思想进行求解。

我们从2开始来计算最大化的乘积M(2)，假设对于整数n我们可以已经知道前面所有的已经确定的最大化乘积(M(i)，i=1…n-1)。
对于给定整数n 我们总能把他分成两部分a(a<n)和n-a，我们只需要遍历a=1…n 求解 $argmax_a M(a)(M(n-a))$ 即可找到最大化的二分割问题
对于任意分割问题，我们总能对分割出的部分进行组合变成一个二分割问题。

2、注

对于2，3来说他们只能分成1，1和1，2，但是如果对于任何大3的数字来说当数字已经被分成2，3就不需要急需细分，因为 $3>1*2,$ $2>1*1$ 。所以说在这里我们进行迭代的时候应该记M(2)=2,M(3)=3，但是在最后展示的时候应该战是M(2)=1, M(3)=2.
对于a的遍历，由于a和n-a是对称的所以我们只需要的对 $a=1...\lceil n/2\rceil$ 遍历即可

综上，我们可以写出代码（python）

class Solution:
    def integerBreak(self, n: int) -> int:
        if n<=3:
           return(max(0,n-1))
        else:
           M = [0 for i in range(n+1)]
           M[2]=2                                            #迭代前设置2，3的值
           M[3]=3
           for i in range(4,n+1):                      
               for j in range(1,(i//2)+1):                   #由于对称性只需要进行前一半的迭代
                   M[i] = max(M[i],M[i-j]*M[j])
           M[2]=1                                            #返回结果前修改2，3作为参数对应的最大乘积
           M[3]=2
           return M[n]

这种解法时间复杂度是 $o(n^2)$ 的，效率一般，

二、数学分析

问题分析

对于2，3我们之前已经讨论过，只有一种分解模式，但是在更大数字分解时如果遇到2，3不做分解可以得到更大的结果。
$4=2+2=3+1$ ， $2*2>3*1$ ，所以对于4来说，分成2和2是更合适的做法。
$6=3+3=2+2+2$ , $3*3>2*2*2$ 该问题中3是一个比2高效的元素
很显然的在进行分解时最优分解中一定不包含1，根据迭代的思想我们可以得知数字的最优分解中的元素应只包含2，3
综上，我们应在分解时尽量多的分解出3，且分解中不包含1，单独列出2，3的情况，我们可以写出一个极简单的代码

class Solution(object):
    def integerBreak(self, n):
        if n<4:
            return n-1
        a=n//3
        b=n%3
        z=[0,1,3]
        return 3**(a-1)*(3+z[b])

该代码只使用了幂函数，所以最终的时间复杂度应该是 $o(log(n))$ 的。

leetcode 343

Leetcode 343

相关推荐