Update integer-break.py

kamyu104 · kamyu104 · commit 70d9981ee459 · 2016-04-20T00:34:58.000+08:00
diff --git a/Python/integer-break.py b/Python/integer-break.py
@@ -56,3 +56,22 @@ def integerBreak(self, n):
         else:                     #  n = 3Q + 4, the max is 3^Q * 2^2
             res = 3 ** (n // 3 - 1) * 4
         return res
+
+# Time:  O(n)
+# Space: O(logn)
+# DP solution.
+class Solution2(object):
+    def integerBreak(self, n):
+        """
+        :type n: int
+        :rtype: int
+        """
+        if n < 4:
+            return n - 1
+
+        # integerBreak(n) = max(integerBreak(n - 2) * 2, integerBreak(n - 3) * 3)
+        res = [0] * 4
+        res[1 % 4], res[2 % 4], res[3 % 4] = 1, 2, 3
+        for i in xrange(4, n + 1):
+            res[i % 4] = max(res[(i - 2) % 4] * 2, res[(i - 3) % 4] * 3)
+        return res[n % 4]
