moonlightshadow123
6/23/2017 - 8:54 AM

279. Perfect Squares

  1. Perfect Squares
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 0
        recd = [n] * (n+1)
        # There are mostly n squares to sum up to `n`.
        recd[0] = 0
        # formular: dp[m] = min{ dp[m - i*i] + 1 },  m - i*i >=0 && i >= 1
        for m in range(n+1):
            i = 1
            while i*i <= m:
                recd[m] = min(recd[m-i*i]+1, recd[m])
                i += 1
        return recd[n]

https://leetcode.com/problems/perfect-squares/#/submissions/1

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.