完美平方

yingl · yingl · commit c5255bf107ad · 2016-08-12T10:44:03.000+08:00
diff --git a/perfect_squares.py b/perfect_squares.py
@@ -0,0 +1,17 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param {int} n a positive integer
+    # @return {int} an integer
+    def numSquares(self, n):
+        # Write your code here
+        # Python效率问题，代码翻译成Java可通过。
+        cache = [2147483647] * (n + 1)
+        cache[0] = 0
+        for i in xrange(n + 1):
+            for j in xrange(1, n + 1):
+                if (i + j * j) <= n:
+                    cache[i + j * j] = min(cache[i + j * j], cache[i] + 1)
+                else:
+                    break
+        return cache[-1]
