LeetCode "Integer Break"

A typical CS style DP based solution:

class Solution(object):
    def __init__(self):
        self.hm = {}

    def integerBreak(self, n):
        if n in self.hm:
            return self.hm[n]
        ret = 0            
        for i in range(1, n//2 + 1):
            v1 = self.integerBreak(i)
            v2 = self.integerBreak(n - i)
            ret = max(ret, v1 * v2, v1 * (n - i), i * v2, i * (n - i))
        self.hm[n] = ret            
        return ret

But there's a Math based solution:

https://leetcode.com/discuss/98249/easy-to-understand-c-with-explanation
In which: "For any integer p strictly greater than 4, it has the property such that 3 * (p - 3) > p, which means breaking it into two integers 3 and p - 3 makes the product larger while keeping the sum unchanged"

原文地址:https://www.cnblogs.com/tonix/p/5411023.html